Functional Programming: This thread is like a burrito

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Functional Programming: This thread is like a burrito

Zemyla: Aug 6, 2008; I'll take her off your hands. Pleasure doing business with you!

gonadic io posted:

Then you'd have 5(?) problems. Lenses have 5 type param these days right?

Apparently, one of the lenses they were going to implement started taking type arguments in the form i m a s t a b u. They took the hint and decided not to implement it.

# ¿ Mar 13, 2016 07:01

Adbot: ADBOT LOVES YOU

# ¿ May 15, 2024 17:33

Zemyla: Aug 6, 2008; I'll take her off your hands. Pleasure doing business with you!

If you were compiling the code, you'd see a much more dramatic decrease in the memory used with foldl', because of something called list fusion. Basically, in GHC, a lot of functions in the Prelude, and a good number of functions in other modules, use rewrite rules to pretend a list is actually a function that produces elements of the list on demand.

The key here is GHC.Base.build, which uses the RankNTypes extension (which allows polymorphism in function arguments):

code:

build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

If you're familiar with the type of foldr, you may notice a similarity between the two. It's intentional, and there is in fact a rewrite rule that says:

code:

forall k z (g :: forall b. (a -> b -> b) -> b -> b)
foldr k z (build g) = g k z

This enables it to directly consume the list as it would have been produced, without producing an intermediate list at all in the first place.

As an example of what this lets you do, let's take a simple function from the Prelude, map:

code:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

Looks pretty simple, huh? Well, the rule-rewriting engine will trigger a transformation into:

code:

{-# RULES "map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs #-}

mapFB :: (b -> r -> r) -> (a -> b) -> a -> r -> r
mapFB c f = \x ys -> c (f x) ys

This basically causes that map code to be turned into a build which uses a foldr on its argument, causing what would be an intermediate list to vanish. Note that this produces a list in the form of build g as well. If the incipient list is turned into an actual list, then another rule fires:

code:

{-# RULES "mapFB" [1] forall f. foldr (mapFB (:) f) [] = map f #-}

This is controlled by inlining level annotations: the [1] means "only use this rule on inlining levels 1 and 0" and [~1] means "use this rule on all levels before 1" - there are 5 levels, and in order they are 4, 3, 2, 1, and 0.

What all this means is that, if you were to use foldl' to do the summation, then the compiler would use rules, inlining, strictness analysis, arity analysis, and others (they're tedious to perform by hand, but not complicated or obscure) to turn:

code:

value :: Int
value = foldl' (+) 0 $ take 10000000 $ repeat 5

into

code:

value :: Int
value = let
    xs !m !z = case m of
        1 -> z + 5
        _ -> xs (m - 1) (z + 5)
    in xs 10000000 0

And a simple tail-recursive function with a strict index can easily be turned into a loop in assembly.

So the lesson is that if you're consuming a list, use either foldr (if you're producing a lazy structure or consuming a possibly-infinite list) or foldl' (if you're producing something strict like a number and you know the list is finite).

Side note: All of this happens if you consume the list at the same time you produce it. If you have a list with a billion elements, calculate its length, and the later calculate its sum, then you're going to be hanging on to a list with a billion elements in memory. Sucks to be you.

# ¿ Apr 17, 2016 07:21

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Functional Programming: This thread is like a burrito