This library is a straightforward combinatorization of the well-known technique of memoization. Let’s start with the canonical example: fib = (map fib’ [0..] !!) where fib’ 0 = 0 fib’ 1 = 1 fib’ n = fib (n-1) + fib (n-2) I interpret what you said to mean that you know how and why this … Read more
Yes, see the parallel package: ls `using` parList rdeepseq will evaluate each element of the list in parallel via the rdeepseq strategy. Note the use of parListChunk with a good chunk value might give better performance if your elements are too cheap to get a benefit evaluating each one in parallel (because it saves on … Read more
One simplification, f_and = liftM2 (&&) f_or = liftM2 (||) or = liftA2 (&&) = liftA2 (||) in the ((->) r) applicative functor. Applicative version Why? We have: instance Applicative ((->) a) where (<*>) f g x = f x (g x) liftA2 f a b = f <$> a <*> b (<$>) = fmap … Read more
Unless you’re deeply into theory, you can regard the Y combinator as a neat trick with functions, like monads. Monads allow you to chain actions, the Y combinator allows you to define self-recursive functions. Python has built-in support for self-recursive functions, so you can define them without Y: > def fun(): > print “bla” > … Read more
Welcome to the world of lazy evaluation. When you think about it in terms of strict evaluation, foldl looks “good” and foldr looks “bad” because foldl is tail recursive, but foldr would have to build a tower in the stack so it can process the last item first. However, lazy evaluation turns the tables. Take, … Read more
The easiest way to understand foldr is to rewrite the list you’re folding over without the sugar. [1,2,3,4,5] => 1:(2:(3:(4:(5:[])))) now what foldr f x does is that it replaces each : with f in infix form and [] with x and evaluates the result. For example: sum [1,2,3] = foldr (+) 0 [1,2,3] [1,2,3] … Read more
I’m not interested in the first definition — those would not help me to write a real program (+1 if you convince me I’m wrong). Please help me understand the second definition. I think map, filter, and reduce are useful: they allow me to program at a higher level — fewer mistakes, shorter and clearer … Read more
How folds differ seems to be a frequent source of confusion, so here’s a more general overview: Consider folding a list of n values [x1, x2, x3, x4 … xn ] with some function f and seed z. foldl is: Left associative: f ( … (f (f (f (f z x1) x2) x3) x4) …) … Read more
A Y-combinator is a “functional” (a function that operates on other functions) that enables recursion, when you can’t refer to the function from within itself. In computer-science theory, it generalizes recursion, abstracting its implementation, and thereby separating it from the actual work of the function in question. The benefit of not needing a compile-time name … Read more