Menu
I'm working through the Haskell book and I've realized I'm having a hard time understanding function composition. At a very basic level I have a mental model of a pipeline that takes an input and passes it's result to the next function in the composition. For simple functions this is very easy.
Where I'm having difficulty is understanding how the resulting type signatures of composing the functions come to be. For example, if we look at the base definition of elem:
elem :: (Foldable t, Eq a) => a -> t a -> Bool
elem = any . (==)
>:t (==)
(==) :: Eq a => a -> a -> Bool
>:t any
any :: Foldable t => (a -> Bool) -> t a -> Bool
I fail to see how the resulting type signature occurs. If I were given the function and asked to write the type signature I'd be hopelessly lost.
The same goes for the following. In the chapter on Traversable we were told that traverse is just sequenceA and fmap composed:
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f
>:t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
>:t sequenceA
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
On their own I understand each functions type signature, but how do they combine to create traverse's type signature?
Super lost here, any help would be greatly appreciated.
511
Composing functions is a common and useful way to create new functions in Haskell. Haskell composition is based on the idea of function composition in mathematics. In mathematics, if you have two functions f(x) and g(x), you compute their composition as f(g(x)). The expression f(g(x)) first calls g and then calls f.
The == is an operator for comparing if two things are equal. It is quite normal haskell function with type "Eq a => a -> a -> Bool". The type tells that it works on every type of a value that implements Eq typeclass, so it is kind of overloaded.
The /= operator means "is not equal". It's supposed to be reminiscent of the mathematical "≠" symbol (i.e., an equals sign with a diagonal line through it).
The Either type is sometimes used to represent a value which is either correct or an error; by convention, the Left constructor is used to hold an error value and the Right constructor is used to hold a correct value (mnemonic: "right" also means "correct").
Perhaps merely visually aligning the types will get you part of the way to some intuition about how the pipeline progresses, and help you make progress towards your next point of confusion!
(==) :: Eq a => a -> (a -> Bool)
any :: (a -> Bool) -> (t a -> Bool)
any . (==) :: Eq a => a -> (t a -> Bool)
To keep the next one on one screen, let's abbreviate Traversable to T and Applicative to A. You also have two fs in your question, one at the computation level and one at the type level. To avoid confusion, I'm going to rename your computation-level f to g instead. So if g :: a -> f b for some Applicative f:
fmap g :: T t => t a -> t (f b)
sequenceA :: (T t, A f) => t (f b) -> f (t b)
sequenceA . fmap g :: (T t, A f) => t a -> f (t b)
\g -> sequenceA . fmap g :: (T t, A f) => (a -> f b) -> t a -> f (t b)
(Wait! How come for fmap g, the constraint on t is Traversable and not Functor? Okay, no problem: we can actually give it the more relaxed type fmap g :: Functor t => .... But since every Traversable must be a Functor, it can also be given this type which makes the parallels more clear.)
188
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
