Saturday 30 April 2016

Haskell: fold pattern


Fold is one of the most useful recursion patterns. For example, suppose you want to calculate
a.   Sum of all elements in a list
b.   Product of all elements in a list
c.    Length of the list

You write program like below.

foldPattern.hs
sumOfElements :: [Integer] -> Integer
sumOfElements [] = 0
sumOfElements (x:xs) = x + sumOfElements(xs)

productOfElements :: [Integer] -> Integer
productOfElements [] = 1
productOfElements (x:xs) = x * productOfElements(xs)

lengthOfList :: [Integer] -> Integer
lengthOfList [] = 0
lengthOfList (x:xs) = 1 + lengthOfList(xs)

*Main> :load foldPattern.hs
[1 of 1] Compiling Main             ( foldPattern.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> sumOfElements [2, 3, 5, -7]
3
*Main> 
*Main> productOfElements [2, 3, 5, -7]
-210
*Main> 
*Main> lengthOfList [2, 3, 5, -7]
4


Let me rewrite the above stuff using fold pattern.

foldPattern.hs
fold :: (a -> b -> b) -> b  -> [a] -> b
fold fun initial []     = initial
fold fun initial (x:xs) = fun x (fold fun initial xs)

sumOfElements = fold (+) 0
productOfElements = fold (*) 1
lengthOfList  = fold addOne 0
 where addOne _ s = 1 + s

*Main> :load foldPattern.hs
[1 of 1] Compiling Main             ( foldPattern.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> sumOfElements [2, 3, 5, -7]
3
*Main> productOfElements [2, 3, 5, -7]
-210
*Main> lengthOfList [2, 3, 5, -7]
4
*Main>

Previous                                                 Next                                                 Home

No comments:

Post a Comment