We can write echoes as a foldr quite handily: To create our echoes function, we will use the prelude function replicate in which replicate n x is a list of length n with x the value of every element. Needless to say, no end will be reached if an input list to foldl is infinite.Īs a toy example, consider a function echoes that takes a list of integers and produces a list such that wherever the number n occurs in the input list, it is replicated n times in the output list. However, a left fold necessarily calls itself recursively until it reaches the end of the input list (because the recursive call is not made in an argument to f). In that case, foldr can move along as much as needed and the compiler will know when to stop. A fold that returns an infinite list is perfectly usable in a larger context that doesn't need to access the entire infinite result. One reason that right-associative folds are more natural in Haskell than left-associative ones is that right folds can operate on infinite lists. When in doubt, stick with foldr or foldl'.įolds and laziness These variants are useful when there is no obvious candidate for the initial accumulator value and we are sure that the list is not going to be empty. With foldl1 and foldr1, all the types have to be the same, and an empty list is an error. Note: Just like for foldl, the Data.List library includes foldl1' as a strict version of foldl1. Will we get True or False for each of the equalities below?įoldl1 :: ( a -> a -> a ) -> -> a foldl1 f = x foldl1 f ( x : xs ) = foldl f x xs foldl1 _ = error "Prelude.foldl1: empty list" Let's examine one such case, involving subtraction as the combining operation. You may notice that in some cases foldl and foldr do not appear to be opposites. The tick), though it might just work if the lists fed to it are not too long.Īre foldl and foldr opposites? There is almost never a good reason to use foldl (without As a rule of thumb, you should use foldr on lists that mightīe infinite or where the fold is building up a data structure and useįoldl' if the list is known to be finite and comes down to a single (imported by adding import Data.List to the beginning of a sourceįile). A tick is a valid character in Haskell identifiers.įoldl' can be found in the Data.List library module "fold-L-tick" or "prime" as in "fold-L-prime". That is strict - it forces the evaluation of f immediately at each step.Īn apostrophe at the end of a function name is pronounced "tick" as in Running out of memory, we have a version of foldl called foldl' However, Haskell is a lazy language, so the calls toį will be left unevaluated by default, thus building up an unevaluatedĮxpression in memory that includes the entire length of the list. For this reason the compiler will optimise it to a Technical Note: foldl is tail-recursive, that is, it recurses
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |