Haskell: Типы функциональной композиции, не соответствующие

Question

У меня возникли проблемы с составом и типами функций. Я хотел бы составить filter (который возвращает список) с len, который принимает список в качестве аргумента (технически Foldable, но я упрощаю здесь). Глядя на типы все это, как и ожидалось:

> :t length 
length :: Foldable t => t a -> Int 

> :t filter 
filter :: (a -> Bool) -> [a] -> [a] 

Так что теперь я ожидал бы тип (len . filter) быть

(length . filter) :: (a -> Bool) -> [a] -> Int 

в то время как в действительности

> :t (length . filter) 
(length . filter) :: Foldable ((->) [a]) => (a -> Bool) -> Int 

Так что, кажется, я потерял некоторые аргументы. Является ли он включенным в требования Foldable каким-то образом я не понимаю?

Обратите внимание, что все работает, как ожидалось, если я частичное применение:

> 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 

Answer 1

Определения:

(.) :: (b -> c) -> (a -> b) -> a -> c 
filter :: (m -> Bool) -> [m] -> [m] 
length :: Foldable t => t n -> Int 

u Что такое?

length . filter :: u 
≡ (.) length filter :: u 

Тогда мы должны решить a, b, c, t, n:

a -> b ~ (m -> Bool) -> [m] -> [m] 
b -> c ~ Foldable t => t n -> Int 

Отсюда следует:

a ~ m -> Bool 
b ~ Foldable t => t n 
b ~ [m] -> [m] 
c ~ Int 

Тривиально:

a = m -> Bool 
b = [m] -> [m] 
c = Int 

Мы должны решить t, n от b ~ Foldable t => t n, т.е. [m] -> [m] ~ Foldable t => t n.

t = ((->) [m]) 
n = [m] 

Поэтому t n = [m] -> [m], который тривиальным образом объединяет.

Сведение:

(.) :: 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 

---

Простой способ понять, почему length . filter не то, что вы хотите посмотреть на определение (.).

(.) g f x = g(f x) 

Поэтому:

(.) length filter 
≡ \x -> length (filter x) 

Мы знаем, что filter x не список.

---

Pointless версии вы можете рассмотреть следующие вопросы:

(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] 

1. Control.Compose
2. Data.Function.Meld
3. Data.Function.Tacit

Answer 2

Право композиция будет:

(length .) . filter :: (a -> Bool) -> [a] -> Int 

что эквивалентно:

\pred xs -> length $ filter pred xs 

как в :

\> let count = (length .) . filter 
\> :type count 
count :: (a -> Bool) -> [a] -> Int 
\> count odd [1..3] 
2 
\> count even [1..3] 
1 

Answer 3

"three laws of operator sections" Используя, мы есть

((length .) . filter) x y = 
(length .) (filter x) y = 
(length . filter x) y = 
length (filter x y) 

и

((length .) . filter) = 
    (.) (length .) filter = 
    (.) ((.) length) filter = 
    ((.) . (.)) length filter 

Последний бит, ((.).(.)), иногда известное как "owl operator", также записывается в виде .: (length .: filter) или fmap . fmap (для функций, fmap является (.)).