(My colleague suggested that I use “Since RECURsion, my hair has grown back” as the title, hahahahaha but I am honest and I have never lost my hair, SO I will not deceive you.)

preface

First, this is a shared post on practicing the basic practice of recursion (baseline + recursion condition) in both Haskell and javascript.

When you solve a problem, imperative languages expect you to give us the steps to solve it, whereas Haskell tends to ask you to provide a description of the problem. So in Haskell, there are no while and for loops, only recursion is used as a solution tool, so recursion is of great importance to Haskell.

Javascript is more flexible, and this flexibility gives us many paradigms to choose from, from while and for imperative problem solving to recursive solving.

Two things, of course:

  1. Haskell syntax is not the focus of this article, but will be covered appropriately.
  2. This article does not represent any practical, but certainly has some learning reference value.

What’s the use of recursion?

Recursion is good at dealing with data structures such as trees and graphs, such as abstract syntax trees and DOM processing. At the same time can elegantly solve some loop statements can not solve the problem.

But there are also cases where stack overflows and memory leaks can be made in the wrong way, or where the code can be obscure, and when you hand it over to a colleague, the other person is confused.

But! Worth learning worth learning worth learning, important things say three times.

The article code

Each function in this article has the same implementation in both languages, Haskell and javascript. For those of you who know a little bit about Haskell like I do, try the Haskell code. But as a front-end engineer, this article will focus on javascript code.

elem

Determines whether the element exists in the element list

Haskell implementation

elem': : (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a `elem'` xs
Copy the code

Js implementation

function elem(a, list) {
  if (list.length === 0) {
    return false;
  }
  if (a === list[0]) {
    return true;
  }
  return elem(a, list.slice(1));
}
Copy the code

Let’s look at the implementation of Haskell:

elem’ :: (Eq a) => a -> [a] -> Bool (Eq a) => a -> [a] -> Bool The elem’ function takes any type A and any type A [] and finally returns a Boolean value type.

(Incidentally, Haskell functions are automatically currified, so the function signature is a -> [a] -> Bool. Because if only one parameter is passed, the signature can be interpreted as: A -> ([a] -> Bool)

The following expressions in elem’ are known in Haskell as pattern matching, which can also be understood as function overloading. There is no syntactic mechanism for function overloading for javascript, but we can artificially simulate overloading with the type and number of arguments.

Therefore, the above two sentences also mean:

Elem ‘a [] = False If the second array argument matches an empty array, False is returned by default

The second sentence elem ‘a (x: xs) | a = = x = True | = aelem’ otherwise xs, where | Haskell called Guards, can also be simply interpreted as if the else or temporarily switch case. (x:xs), much like destructuring assignment in ES6, cuts the arraylist argument passed for matching into the first element X and all remaining elements xs. Therefore, if a==x, it returns True; otherwise, it recurses to determine whether a is in the remaining array of XS.

Note above that in the elem’ function, the basis for recursion, also known as the boundary condition, is either a [] = False or a == x = True. And the recursion conditions are x:xs and a elem’ xs.

That’s how elem’ recursion works in Haskell.

So if you don’t understand haskell, you can just look at the javascript recursion above.

Again, the basis for recursion is two if judgments that return both nonexistence and existence. The recursive condition is elem(a, list.slice(1)). If the above two boundary conditions are triggered, the list of elements will be narrowed down and recursively judged again.

Normal solutions: include, indexOf, lastIndexOf

sum

Numeric list summation

Haskell implementation

sum': :Num a => [a] -> a
sum' []  = 0
sum' (x:xs) = x + sum' xs
Copy the code

Js implementation

function sum(list) {
  if (list.length === 0) {
    return 0;
  }
  return list[0] + sum(list.slice(1));
}
Copy the code

So again, we’re going to use the recursion criteria plus the recursion conditions.

We even get a definition of the problem: the sum of a list of numbers must equal the sum of the first number and the sum of the rest of the list.

List.reduce ((a, b) => a + b)

maximum

Find the maximum value of the list of numbers

Haskell implementation

maximum': : (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
Copy the code

Js implementation

function maximum(list) {
  if (list.length === 0) {
    throw new Error('maximum of empty list');
  }
  if (list.length === 1) {
    return list[0];
  }
  return Math.max(list[0], maximum(list.slice(1)));
}
Copy the code

Normal solution: of course math.max (1,2,30,4,5) is straightforward.

repeat

Repeat a value

Haskell implementation

repeat' :: a -> [a]
repeat' x = x:repeat' x
Copy the code

Js implementation

function repeat(x) {
  return [x].concat(repeat(x));
}
Copy the code

The interesting thing here is that Haskell itself is lazy computing, so the same implementation would stack over in javascript, whereas in Haskell it would work fine, as follows: take 5 tells Haskell to only need 5 repeat values. So they stopped in time.

Prelude> take 5 (repeat "*")
["*"."*"."*"."*"."*"]
Copy the code

replicate

Repeat a value a fixed number of times

Haskell implementation

replicate': : (Num i, Ord i) => i -> a -> [a]
replicate' n x
    | n <= 0    = []
    | otherwise = x:replicate' (n- 1) x
Copy the code

Js implementation

function replicate(n, x) {
  if (n <= 0) {
    return [];
  }
  return [x].concat(replicate(n - 1, x));
}
Copy the code

Again, not much.

But the normal way for people to do it, or “?” .repeat(n).split(”)

reverse

An array of reverse

Haskell implementation

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
Copy the code

Js implementation

function reverse(list) {
  if (list.length === 0) {
    return [];
  }
  return reverse(list.slice(1)).concat(list[0]);
}
Copy the code

The reverse result of an array is equal to the result of pushing the first element into the rest of the array that has already been reversed.

take

Take the first n entries of an array element

Haskell implementation

take': : (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0   = []
take' _ []     = []
take' n (x:xs) = x : take' (n- 1) xs
Copy the code

Js implementation

function take(n, list) {
  if (n <= 0) {
    return [];
  }
  if (list.length === 0) {
    return [];
  }
  return [list[0]].concat(take(n - 1, list.slice(1)));
}
Copy the code

So the basic feeling here is kind of a recursive idea of writing a hundred different functions.

Normal solution: Slice, of course

zip

Pairs the elements of two arrays

(We can understand as, as possible group cp hahaha)

Haskell implementation

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip'_ = [] []zip' (x:xs) (y:ys) = (x,y):zip' xs ys
Copy the code

Js implementation

function zip(list1, list2) {
  if (list1.length === 0) {
    return [];
  }
  if (list2.length === 0) {
    return [];
  }
  return [[list1[0], list2[0]]].concat(zip(list1.slice(1), list2.slice(1)));
}
Copy the code

Zip in Haskell packs two arrays into pairs of tuples.

Prelude> zip ["a"."b"."c"] [1, 2, 3] [("a", 1), ("b", 2), ("c"And 3)]Copy the code

Since there are no tuples in javascript, you can only simulate them with arrays.

> zip(["a"."b"."c"[[], [1, 2, 3])'a', 1], ['b', 2], ['c', 3]]Copy the code

The ZIP function looks a little complicated, but if you take a closer look, it’s really no more than that, right?

quicksort

Quick sort

Haskell implementation

quicksort: : (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in smallerSorted ++ [x] ++ biggerSorted
Copy the code

Js implementation

function quicksort(list) {
  if (list.length === 0) {
    return [];
  }
  let x = list[0];
  let rest = list.slice(1);

  let smallerSorted = quicksort(rest.filter(i= > i <= x));
  let biggerSorted = quicksort(rest.filter(i= > i > x));

  return [smallerSorted, x, biggerSorted].flat();
}
Copy the code

The quicksort ‘method [a | a < – xs, a < = x] USES a haskell interesting List comprehensions, collection of this kind of writing is a bit like in mathematics.

In javascript, can write two filter replacement [a | a < – xs, a < = x], and [a | a < – xs, a > x].

The definition of the algorithm, of course, is that the sorted array takes all the elements less than or equal to the head first (which are sorted), followed by the elements greater than the head (which are sorted as well). The difference here is that because there are two sorts in the definition, we recurse twice! ~

This function implementation really demonstrates the beauty of recursion, right

Write in the last

This article is of interest ~ it seems to be a boring article, HMM.