Assign and . The application
s y x forces for a fresh type ; applying f to that result forces . No further equations identify these four type variables. The principal type is thereforek :: (u -> v -> w) -> v -> (w -> r) -> u -> r
k s x f y = f (s y x)Every compatible typing is an instance of this one, because type inference imposed precisely the two application constraints and no class constraints.
Suppose with the same integer result type. The empty list forces . The two singleton calculations force and . But thencontrary to . No such
c,b exist. This is the information restriction in the fold factorisation criterion: equal folded tails must remain indistinguishable after the same head is attached. A larger, function-valued result type can retain the missing information, as the continuation representation of a left fold does below.For every accumulator , pattern matching makes
foldl s a undefined the bottom value. Now use structural induction on a finite list prefix ending in the bottom value. The induction step is foldl s a (x:ps) = foldl s (s a x) ps; the induction hypothesis applies to every accumulator, including s a x. Consequently every such finite approximation has result .An infinite lazy list is the limit of its finite prefixes, each interpreted as a finite approximation of a lazy list. Definable Haskell operations are Scott continuous maps, so the result on the infinite lazy list is the supremum of the results on these approximations. Every result is , hence
foldl s a xs = undefined on every infinite input spine, irrespective of whether s would inspect the accumulator.For a concrete separation, choose
s = (&&), a = True, and xs = False : repeat True. The left fold is , whereas the right fold returns False after observing the first element: False && r does not demand r. It is reaching the end of the input spine, rather than strictness of the combining operation, that prevents this left fold from returning.The right fold replaces the two list constructors by its two arguments; the left fold instead updates an accumulator while traversing the list.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c z [] = z
foldr c z (x:xs) = c x (foldr c z xs)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl s a [] = a
foldl s a (x:xs) = foldl s (s a x) xsThus
foldr is the natural list fold: it preserves the constructor arrangement while replacing [] by z and (:) by c. In particular, foldr (:) [] = id. More generally, the fold factorisation criterion says that the defining equations characterize the corresponding structural recursion. Association and lazy evaluation are separate: the accumulator in this definition of left fold is not automatically evaluated at each step.[ref]Haskell 2010 Language Report. Chapter 9, PreludeList: foldr and foldl
By linearity of expectation, . Expanding the square and again using linearity of expectation givesHere the zero means imply and . The covariance expansion itself does not require independence. Under the additional independence stated here, , so it simplifies further to .
There are unlisted articles, also show them or only show them.