Bearing the above

In the end, I mentioned an example of traversing prime numbers on Haskell’s official website

primes = filterPrime [2..]
  where filterPrime (p:xs) =
          p : filterPrime [x | x <- xs, x `mod` p /= 0]
Copy the code

In this article, we’ll look at each of the concepts involved.

List

A List in Haskell is a single-type data structure, which means that only one type of data can be stored in a List. You can’t store different types of data like arrays in JS.

let demoList = [1.2.3.4] Correct -)
let wrongDemoList = [1.2.3, '4'] -- × wrong, raise an error
Copy the code

:Operator command

The: operator can combine an element with a List. For example, the result of 1:[2,3,4] is [1,2,3,4], and [1,2,3,4] can be interpreted as 1:2:3:4:[].

Prelude> "Hello" : ["Lilei"]
["Hello"."Lilei"]
Prelude> 1: [2.3.4]
[1.2.3.4]
Copy the code

When processing function arguments, if the argument is a List, we can use the x:xs mode to represent the first element and the rest of the argument List, as in the example filterPrime (p:xs). If filterPrime [1,2,3,4] is executed, then p corresponds to 1. Corresponding [4] 2 xs

When I first came into contact with X: XS, I felt similar to the syntax of deconstructing assignment in JS.

function getArgs([x, ...xs]){
    console.log('x = ', x)
    console.log('xs =', xs)
}
/**
 *  getArgs([1,2,3,4]) =>
 *  x = 1
 *  xs = [2,3,4]
*/
Copy the code

Range

I think everyone has the experience of writing a list of numbers on a piece of paper. When a list of numbers is long, many people abbreviate it to something like 1,2,3… The form of ten, that’s very intuitive. Range is such an intuitive List constructor. From Range we can not only use [1..10] for [1,2,3,4,5,6,7,8,9,10], but also use [‘A’..’Z’] for all uppercase letters.

Prelude> [1.20.]
[1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20]
Prelude> ['K'..'Z']  
"KLMNOPQRSTUVWXYZ"
Copy the code

Haskell even supports automatic derivation of a Range’s step size. For example, we can represent all even numbers between 0 and 50 like this:

Prelude> [0.2.. 50]
[0.2.4.6.8.10.12.14.16.18.20.22.24.26.28.30.32.34.36.38.40.42.44.46.48.50]
Copy the code

Due to Haskell’s lazy evaluation characteristics, such as [2..] This kind of List of infinite length is also declarable. Hakell, however, does not evaluate the entire List when it is declared. Instead, Hakell evaluates the List as needed when it participates in the operation.

Prelude> take 10 [2..] ,3,4,5,6,7,8,9,10,11 [2]Copy the code

We can think of this infinite list as an initial number plus a rule of evolution

Note: take is a function related to List, used to get the first n items of List

List Comprehension

List Comprehension is translated in Haskell Functional Programming as List generator, which is also known as List Comprehension. Whatever the translation, List Comprehension is essentially the way a List + rule = a new List is constructed, which is not unrelated to, but identical to, the way a new set is defined in mathematics based on an initial set.


S = x squared ∣ x ∈ 1.. 100 . x < 10 S = {x squared | x ∈ {1.. 100}, x < 10 }

The above formula represents the set of squares of positive integers up to 10, which can be written in Haskell as follows:

Prelude> [x^2 | x <- [1.100.], x < 10]
[1.4.9.16.25.36.49.64.81]
Copy the code
  • x<-[1..100]Represents the original list.
  • After a commax < 10Represents filter criteria for list data. There can be multiple filter criteria, separated by commas.
  • |On the left side of thex^2Is an output function that processes filtered list data

Multiple filter conditions

Prelude> [x^2 | x <- [1.100.], x < 10, x > 4]
[25.36.49.64.81]
Copy the code

Filter uppercase letters in the string through List Comprehension

Prelude> filterUpper st = [x| x <- st, x `elem` ['A'..'Z']]
Prelude> filterUpper "Hello World"
"HW"
Copy the code

The Where keyword

The where keyword is used to define functions that are visible only within the current function.

sayHiToOthers xs = [sayHi x | x <- xs]
  where sayHi x = "Hi " ++ x
Copy the code

With the WHERE keyword we define the function sayHi, which can only be used in sayHiToOthers, and build a new List using the sayHi function

Prelude> sayHi ["LiLei"."HanMeimei"]
["Hi LiLei"."Hi HanMeimei"]
Copy the code

Eratosthenes sieve method

The Sieve method of Eratosthenes is one of the most effective methods to find all prime numbers in a certain range, named after the ancient Greek mathematician Eratosthenes. Please refer to the description of its calculation in Baidu Encyclopedia.

To get all the primes within n of the natural number, we must set the values not greater thanAll the multiples of the prime of, and what’s left is the prime.

Given the range n of values to be screened, find the prime numbers within. First use 2 to sieve, that is, leave the 2, the multiples of 2 out; I’m going to take the next prime number, which is 3, and I’m going to keep the 3, and I’m going to get rid of multiples of 3; And then we use the next prime number, 5, and we keep the 5, and we get rid of the multiples of 5; Keep repeating…… .

To summarize

primes = filterPrime [2..]
  where filterPrime (p:xs) =
          p : filterPrime [x | x <- xs, x `mod` p /= 0]
Copy the code

With that in mind, let’s look at the example at the beginning of this article.

  • throughwhereKeyword, we areprimesI’ve defined a name calledfilterPrimeThe function of
  • filterPrimeThe function takes aListAs a parameter, the calculation result is determined byListThe first element ofp, andfilterPrimeA combination of the results of recursive calls themselves.
  • With reference toEratosthenes sieve method.filterPrimeWhen recursively calling itself, the argument passed isThe initial ListGet rid of the first elementPAnd then the rest of itxsThe exclusion of which can bepDivisible elementsList.
  • Due to / 2.. Is a List of infinite length, so obviouslyfilterPrimeThere is no endpoint to the recursive call toprimesIs a List of infinite length.

Explore the implementation of filterPrime

-- In the first step, we get 2: xs, where xs represents a positive number greater than 2 and not divisible by 2 -- in the second step, we get 2:3: XSS, where XSS represents a positive number greater than 3 and not divisible by 2, 3 -- in the third step, we get 2:3:5: XSSS, XSSS stands for positive numbers greater than 5 and not divisible by 2, 3, and 4...Copy the code

So far we have completed the Haskell implementation of eratostinian sieve for screening prime numbers.

Next

Unlike JS, Haskell is a strongly typed language. The type system in Haskell is so important that it has been described as the first big obstacle to learning Haskell.