Search code examples
haskelltypestype-systemsdependent-type

What would the type of a list of cascading functions be?

In Haskell syntax, we can have a (abstract) type like [a -> b], which is a list of functions a to b. A concrete type of this would be [Int -> Int], such as map (*) [1..10]. Is it possible to have a list of cascading functions in a type like [a -> b, b -> c, c -> d, ...]? The individual elements of the list are all different (I think) so I don't think it's possible. But is it possible with dependent types? What would its type signature be (preferably in pseudo-Haskell syntax)?

Solution

  • You can't do that with a plain list, but you could construct your own list-like type as follows:

    {-# LANGUAGE GADTs #-}

data CascadingList i o where
    Id :: CascadingList i i
    Cascade :: (b -> o) -> CascadingList i b -> CascadingList i o

    Then you could make these CascadingLists as follows:

    addOnePositive :: CascadingList Int Bool
addOnePositive = Cascade (>0) $ Cascade (+1) $ Id

    You could 'collapse' the lists:

    collapse :: CascadingList a b -> a -> b
collapse Id = id
collapse (Cascade f c) = f . collapse c

    Then you would have

    collapse addOnePositive 0 == True

    Note that this does not take into account the types of the intermediate functions, so it may not be what you are looking for.

    I've just realised that this is closer to something like [c -> d, b -> c, a -> b]. It's an easy change to make it closer to your intentions; I could edit it but I think you get the idea.