I am having some troubles with function composition and types.
I would like to compose filter (which returns a list) with len, which takes a list as an argument (technically a Foldable but I am simplifying here).
Looking at the types everything is as expected:
> :t length
length :: Foldable t => t a -> Int
> :t filter
filter :: (a -> Bool) -> [a] -> [a]
So now I would expect the type of (len . filter) to be
(length . filter) :: (a -> Bool) -> [a] -> Int
while in reality is
> :t (length . filter)
(length . filter) :: Foldable ((->) [a]) => (a -> Bool) -> Int
So it seems I lost some arguments. Is it included in the the Foldable requirements in some way I am not understanding?
Note that everything works as expected if I do partial application:
> let myFilter = filter odd
> :t myFilter
myFilter :: Integral a => [a] -> [a]
> :t (length . myFilter)
(length . myFilter) :: Integral a => [a] -> Int
> (length . myFilter) [1,2,3]
2
Definitions:
(.) :: (b -> c) -> (a -> b) -> a -> c
filter :: (m -> Bool) -> [m] -> [m]
length :: Foldable t => t n -> Int
What is u?
length . filter :: u
≡ (.) length filter :: u
Then we must solve a, b, c, t, n:
a -> b ~ (m -> Bool) -> [m] -> [m]
b -> c ~ Foldable t => t n -> Int
It follows:
a ~ m -> Bool
b ~ Foldable t => t n
b ~ [m] -> [m]
c ~ Int
Trivially:
a = m -> Bool
b = [m] -> [m]
c = Int
We have to solve t, n from b ~ Foldable t => t n, i.e. [m] -> [m] ~ Foldable t => t n.
t = ((->) [m])
n = [m]
Therefore, t n = [m] -> [m] which trivially unifies.
Summarising:
(.) :: Foldable ((->) [m]) =>
(([m] -> [m]) -> Int)
-> ((m -> Bool) -> [m] -> [m])
-> (m -> Bool) -> Int
filter :: (m -> Bool) -> [m] -> [m]
length :: Foldable ((->) [m]) => ([m] -> [m]) -> Int
(.) length filter :: Foldable ((->) [m]) => (m -> Bool) -> Int
An easier way to understand why length . filter is not what you want is to look at the definition of (.).
(.) g f x = g(f x)
Therefore:
(.) length filter
≡ \x -> length (filter x)
We know that filter x is not a list.
Pointless versions you may consider:
(length .) . filter
filter >=> return . length
(fmap.fmap) length filter
(id ~> id ~> length) filter -- [1]
filter $* id $$ id *$ length -- [2]
lurryA @N2 (length <$> (filter <$> _1 <*> _2)) -- [3]