Ruby/Haskell. Left and right folds

Haskell has ample opportunities to work with lists, in particular - left and right fold. For this in the Prelude module there are functions such as foldr - for the right fold and foldl - for the left fold:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f ini []     = ini
foldr f ini (x:xs) = f x (foldr f ini xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f ini []     = ini
foldl f ini (x:xs) = foldl f (f ini x) xs
For an example of their use let's implement the function evenOnly, which throws out elements from the list that stand in odd places, leaving only even ones. One of the implementations is as follows:

evenOnly :: [a] -> [a]
evenOnly = fst . foldr (\x (y1, y2) -> (y2, x:y1)) ([],[])
To do this, we used the right fold. Consider how Haskell will step by step perform the reductions with the fold of the list [1, 2, 3, 4].
Denote the anonymous function (\ x (y1, y2) -> (y2, x: y1)) by f

{- Right fold of list (steps of reductions):
foldr f ([],[]) 1:2:3:4:[]
~> f 1 (foldr f ([],[]) 2:3:4:[])
~> f 1 (f 2 (foldr f ([],[]) 3:4:[]))
~> f 1 (f 2 (f 3 (foldr f ([],[]) 4:[])))
~> f 1 (f 2 (f 3 (f 4 (foldr f ([],[]) []))))
~> f 1 (f 2 (f 3 (f 4 ([],[]))))
~> f 1 (f 2 (f 3 ([],4:[])))
~> f 1 (f 2 (4:[], 3:[]))
~> f 1 (3:[], 2:4:[])
~> (2:4:[], 1:3:[])
([2,4], [1,3])
-}
Let's change the right fold to the left in this implementation:

evenOnly :: [a] -> [a]
evenOnly = fst . foldl (\(y1, y2) x -> (y2, x:y1)) ([],[])
And also let's look how reductions will be executed step by step.

{- Left fold of list (steps of reductions):
foldl f ([],[]) 1:2:3:4:[]
~> foldl f (f ([],[]) 1) (2:3:4:[])
~> foldl f (f (f ([],[]) 1) 2) (3:4:[])
~> foldl f (f (f (f ([],[]) 1) 2) 3) (4:[])
~> foldl f (f (f (f (f ([],[]) 1) 2) 3) 4) []
~> f (f (f (f ([],[]) 1) 2) 3) 4
~> f (f (f ([],1:[]) 2) 3) 4
~> f (f (1:[],2:[]) 3) 4
~> f (2:[], 3:1:[]) 4
~> (3:1:[], 4:2:[])
([3,1], [4,2])
-}
From these examples we can see how the right and left folds differ. Also note that the implementation of evenOnly through left fold certainly behaves incorrectly, because the order of the "even" values becomes incorrect. Also pay attention to the difference of signatures of anonymous functions passed to the functions foldr and foldl. Now we will try to implement similar functionality on Ruby. First, let's implement the functions foldr and foldl:

def foldr(f, ini, list)
  return ini if list.length == 0
  *xs, x = list
  foldr(f, f.call(x, ini), xs)
end

def foldl(f, ini, list)
  return ini if list.length == 0
  x, *xs = list
  foldl(f, f.call(ini, x), xs)
end
Based on the right fold:

evenOnly = ->(list) { foldr(->(x, ini) { xs, ys = ini; [ys, [x, *xs]] }, [[], []], list).first }
Based on the left fold:

evenOnly = ->(list) { foldl(->(ini, x) { xs, ys = ini; [ys, [x, *xs]] }, [[], []], list).first }
Since the left fold is incorrect (given only for demonstration), we take the right fold as the basis and run our implementation for the test a couple of times:

evenOnly.call([])                              # []
evenOnly.call([1])                             # []
evenOnly.call([1, 2, 3, 4])                    # [2, 4]
evenOnly.call([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) # [2, 4, 6, 8, 10]

No comments :

Post a Comment