Fun with Functions

Pete Nuttall writes about the fnreduce function:

fnreduce :: [(a->a)]->a->a
fnreduce [] value = value
fnreduce (a:as) value = freduce as $ a value

A shorter, although not necessarily clearer, expression of this function would be

fnreduce as value = (foldr (flip (.)) id as) value

This just says that to apply a list of functions to a value, we first compose all the functions by folding down the list, then apply the result to the value. The important thing here is (flip (.)), which says to compose backwards; it means that fnreduce [f, g, h] returns (h . g . f . id) instead of (f . g . h . id). An interesting side note is that it doesn't matter (from a semantic point of view) whether I use foldl or foldr, since function composition is associative:

f . (g . (h . id)) = ((id . f) . g) . h

But "flip" here feels a little confusing. A clearer approach would be to reverse the list instead of reversing the operator:

fnreduce as value = foldr (.) id (reverse as) value

This might be less efficient, but it says in a much clearer way what I'm doing.

Yet another option is to eschew the use of function composition:

fnreduce as value = foldl (flip ($)) value as

Here ($) is the application function; (f$x) applies f to x. So if we reverse it (call this $$), we get (x$$f) applies f to x. Folding this from the left down the list [f, g, h] gives us (((value$$f)$$g)$$h), which is exactly what the original fnreduce did.

I think this is maybe the best fold-based solution to the original problem, because it models what's happening (repeatedly transforming a value with a series of functions) directly. To use a right-fold, you have to remove the flip and reverse as (the reason this is necessary is left as an exercise to the reader).

---

Pete also asks whether this can be done for heterogenous lists in a type-safe manner. The core problem is, what is the type of our list? It can't actually be a list: in order to check that it's OK to combine the output of one function with the input of another, we would need the elements of the list to have different types. You can't do this in Haskell, even a crazy ghc-extended Haskell.

So, we could try something like this:

module Test where

data TransformList a b where
    Nil   :: TransformList a a
    Cons  :: (a -> b) -> TransformList b c -> TransformList a c

apply :: TransformList a b -> a -> b
apply Nil         = id
apply (Cons f fs) = (apply fs) . f

This lets us do stuff like

> apply (Cons (\x -> x + 1) (Cons (\x -> show x) Nil)) 5
"6"

This is cute, but I don't know that it's really that useful. After all, how is it any better than the following?

> ((\x -> show x) . (\x -> x + 1)) 5
"6"

Everything the above code lets you do with TransformList could just as well be done with the humble compose operator. The only benefit would be if we could somehow do "list-like" stuff with a transform list. For instance, say we want to write the following function:

traceIntermediates Nil        x = (x, [])
traceIntermediates (Cons f l) x = let x'        = f x
                                      (x'', ss) = traceIntermediates l x'
                                  in
                                    (x'', (show x'):ss)

This won't compile, because we don't know that x' is a member of the Show typeclass. And there is no way to fix this in a reusable way using any technique that relies on building a type parameterized on the input and output types: the problem is that we need to say something about the types of the intermediate values, but their type variables are inaccessible.

In other words, there isn't any way to write down a constraint on the type "TransformList a b" that constrains the intermediates. So I've just wasted a lot of typing duplicating the compose operator. Yay.

On the other hand, it's entirely possible to do this if you don't mind some boilerplate code.

data ShowTransformList a b where
    Nil   :: (Show a) => ShowTransformList a a
    Cons  :: (Show a, Show b, Show c) => (a -> b) -> ShowTransformList b c -> ShowTransformList a c

traceIntermediates :: ShowTransformList a b -> a -> (b, [String])
traceIntermediates Nil        x = (x, [])
traceIntermediates (Cons f l) x = let x'        = f x
                                      (x'', ss) = traceIntermediates l x'
                                  in
                                    (x'', (show x'):ss)

apply :: ShowTransformList a b -> a -> b
apply Nil         = id
apply (Cons f fs) = (apply fs) . f

Now I can do this:

> traceIntermediates
    (Cons (\x -> x + 1)
          (Cons (\x -> x * 2)
                (Cons (\x -> x - 5)
                      (Cons show
                            (Cons (read :: String -> Double)
                                  Nil))))) 5
(7.0,["6","12","7","\"7\"","7.0"])