How to define a multiple composition function?

Question

Is there a way to define a Haskell function that takes a (some kind of collection) of functions and produces a single function: their composition from right to left?

I tried:

foldr ($)

but this only accepts a list of functions whose result has the same type as that of their argument:

foldr ($) :: a -> [a -> a] -> a

So, I can do:

foldr ($) 5 [(+) 1, (*) 2] and this produces the correct result 11

However trying to evaluate this:

foldr ($) "hello" [(+) 1, length]

produces the error below:

ERROR - Type error in list

*** Expression : [(1 +),length] *** Term : length *** Type : [a] -> Int *** Does not match : Int -> Int

Answer 1

As always, let's put type annotations everywhere.

-- foldr ($) "hello" [(+) 1, length]
($) :: (a -> b) -> a -> b
"hello" :: [Char]
(+) 1 :: Num a => a -> a
length :: [a] -> Int
[(+) 1, length] :: ?!

Native Haskell lists cannot contain items of different types.

So let's back up a step. I'll use < and > to denote "the list-ish thing we want." We don't want a collection of randomly-typed things. < (+) 1, length > is okay, but < length, (+) 1 > is not, or rather we'd need an instance Num [a]. Similarly if we have more than two items: each item's type is necessarily related to its neighbors. Furthermore, the type of the overall list is related only to the types of the first and last members: what's the starting and ending type?

We can do this with GADTs:

{-# LANGUAGE GADTs #-}
module SO26565306 where

data F a b where
  FNil :: F a a
  (:&) :: (b -> c) -> F a b -> F a c

infixr 5 :&

runF :: F a b -> a -> b
runF FNil = id
runF (f :& fs) = f . runF fs

f :: F [a] Int
f = (+) 1 :& length :& FNil

ghci> runF f "hello"
6

The value f is the implementation of your desired < (+) 1, length > "list".

There's some further elaboration of F possible--Functor and Category instances, for example--but I don't really see much use for it. All we've done is artificially impose a data structure on ordinary function composition. We can't even use GHC's overloaded list notation, which isn't (yet?) sufficiently flexible. Furthermore, interposing all the GADT constructors will block optimizations, almost certainly including list fusion. (I haven't experimented or thought through it carefully.)

Answering Your Question

Yes, it's possible to define a Haskell function that takes a collection of functions, of varying but composable types, and produces their composition. The collection type I've demonstrated needs the GADTs extension, which is not available in Hugs, the compiler you seem to be using. Furthermore, you can't really do much with the collection. I've not proved it, but I'll assert that there's nothing you can do with a value of type F a b that you can't do with a value of type a -> b, other than decomposing it into its component functions by pattern-matching.

In other words, what you're asking about is indeed expressible in Haskell, it's just not clear that there's any advantage to doing it in this way.

Other Questions

As we've discussed in the comments, it seems you're looking for a Haskell analogy for Clojure transducers. Would you like to open a new question on that topic? It's a bit more precise and focused differently than this one.

The Bottom Line

Why not just use ((+) 1) . length?

Answer 2

Haskell List only allows elements of the same type. So just like you can't have

["one", 2]

because "one" is a String and 2 is an Int. You also can't have

[(+) 1, length]

Because (+) 1 is a Int -> Int and length is a [a] -> Int