Haskell: 函数组合类型不匹配

Question

我在函数组合和类型方面遇到了一些麻烦。我想用 len 组合 filter（其中 returns 一个列表），它以一个列表作为参数（技术上是 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

正确的构图应该是：

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

定义：

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

我们必须从b ~ Foldable t => t n解出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 不是列表。

您可能会考虑无意义的版本：

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

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

Haskell: 函数组合类型不匹配

Haskell: Types of function composition not matching

haskell

types

functional-programming

combinators

function-composition