Geek Answers Handbook

Various folds in Haskell and SML / NJ

In the definition of foldl, it is possibly incorrect in SML / NJ 110.75 , I found that there is a relation foldl (op -) 2 [1] = foldr (op -) 2 [1]. But when I tried the above in Haskell, I found that the aforementioned relation rewritten in Haskell foldl (-) 2 [1] == foldr (-) 2 [1]does not work. Why is this? Does Haskell have a different definition for fold than SML / NJ?

thanks

+4
source share
4 answers

In short, they are essentially the same, with one minor difference: the order of the arguments passed to the operator (the union function that you pass to collapse) is reversed. And since subtraction is not commutative, it will give different results.

In Haskell (as well as OCaml, C ++, Clojure, Common Lisp, Erlang, F #, JavaScript, PHP, Python, Ruby, Scala, and many others), for foldl, the first function argument is the initial value or the "added value to so far, "and the second argument is an item from the list.

However, in standard ML, the first argument to the function is an element from the list, and the second argument is the initial value or “still added value”.

"" "". - . , Haskell , . "" , . SML , ? . , foldl foldr .

+3

ML :

val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Haskell :

foldl :: (a -> b -> a) -> a -> [b] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b

Haskell foldl - .

, , foldr - , , , :

foldr f init [x1, x2, ..., xn]    
 ==> f(x1, f(x2, ..., f(xn, init)...))

-, ML

foldl f init [x1, x2, ..., xn]
 ==> f(xn,...,f(x2, f(x1, init))...)

, ML foldl - , , .

Haskell

foldl f init [x1,x2,.....,xn]
 ==> f(f(...f(f(init,x1),x2),.....),xn)

haskell foldl , , .

ML f(x1,init), x1 - init, , foldr xn - init, .

, Haskell f(init,x1), init - x1. .

ML foldl:

foldl (op -) 100 [1,2,3,4]
 ==> 4 - (3 - (2 - (1 - 100)))
 ==> 102

ML/Haskell foldr:

foldr (-) 100 [1,2,3,4]    or    foldl (op -) 100 [1,2,3,4]
 ==> 1 - (2 - (3 - (4 - 100)))
 ==> 98

Haskell foldl:

foldl (-) 100 [1,]
 ==> (((100 - 1) - 2) - 3) - 4
 ==> 90

, foldl. ML left , Haskell left .

, , . ( init x1 , , .)

+8

?

mlFoldl :: (a -> b -> b) -> b -> [a] -> b
mlFoldl f = foldl (flip f)
+5

:

Haskell Wiki:

-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

foldl (-) 2 [1] (2 - 1) foldr (-) 2 [1] (1 - 2)

SML

foldl f init [x1, x2, ..., xn]
    returns

    f(xn,...,f(x2, f(x1, init))...)

    or init if the list is empty.

foldr f init [x1, x2, ..., xn]
    returns

    f(x1, f(x2, ..., f(xn, init)...))

    or init if the list is empty.

therefore foldl (op -) 2 [1]- fxn - init or 1 - 2, and foldr (op -) 2 [1]- fx1 - init. This is still 1 - 2, but only by coincidence. The answers diverge from a longer list, but not as much as the answers between Haskell and SML.

+2
source

More articles:


All Articles