haskell - 为什么高阶函数会返回这种(意外的)类型？

Question

对 haskell 类型感到困惑 [*]

我开始学习 haskell，并对 haskell 类型推断的结果感到困惑(参见下面的示例)。不幸的是，我对 haskell 的掌握不够流利，无法提出真正的问题，所以我必须通过示例来工作。

[*]一旦我知道真正的问题，我就会更新标题..

我的目标

我正在关注Get programming with haskell书。第 10 课展示了一种“保持状态”的方法:

-- The result of calling robot (`r`) is a function that takes 
-- another function (`message` as argument). The parameters 
-- passed to the initial call to `robot` are treated 
-- as state and can be passed to `message`.
-- 
robot name health attack = \message -> message name health attack

getName r = r (\name _ _ -> name)

klaus = robot "Klaus" 50 5

*Main> getName klaus
"Klaus"

我想我理解了它的要点，并尝试创建一个小小的机器人战斗。最后我想要这样的东西:

klaus = robot "Klaus" 50 5
peter = robot "Peter" 50 5

victor = fight klaus peter

getName victor
-- should be "Klaus"

我的机器人

这是我编写的实现:

robot name health attack = \message -> message name health attack

isAlive r = r (\_ health _ -> health > 0)

fight attacker defender = if isAlive attacker then
                             attacker
                          else
                             defender



printRobot r = r (\name health  attack -> "Name: " ++ (show name) ++", health: " ++ (show health) ++ ", attack: " ++ (show attack))

klaus = robot "Klaus" 50 5
peter = robot "Peter" 60 7

在 ghci 中进行实验

代码在 ghci ( :l robots.hs ) 中加载。当我试验我的代码时，我发现事情并不完全按计划进行:类型系统和我似乎对结果类型有不同的想法。

请指出我的推理错误的地方，并帮助我理解我的方法的错误:-)

--
-- in ghci
--

*Main> :t klaus
-- I understood: 
-- klaus is a function. I have to pass a function that
-- takes name, health, and attack as parameters and 
-- returns something of type "t". 
--
-- A result of same type "t" is then returned by calling klaus
klaus :: ([Char] -> Integer -> Integer -> t) -> t

-- check the "isAlive" function:
-- As expected, it returns a Bool
*Main> :t isAlive klaus
isAlive klaus :: Bool

-- This is also expected as klaus has health > 0
*Main> isAlive klaus
True

-- Inspecting the type of `isAlive` confuses me:
--
-- I do understand:
--
-- The first parameter is my "robot". It has to accept a function
-- that returns a boolean (basically the isAlive logic):
--
-- (t1 -> a -> t -> Bool) 
-- - t1: name, ignored
-- - a: health, needs to be a comparable number 
-- - t: attack value, ignored
-- - returns boolean value if the health is >0
--
-- What I do NOT understand is, why doesn't it have the following type
-- isAlive :: (Ord a, Num a) => (t1 -> a -> t -> Bool) -> Bool
*Main> :t isAlive
isAlive :: (Ord a, Num a) => ((t1 -> a -> t -> Bool) -> t2) -> t2

-- The signature of `isAlive` bites me in my simplified 
-- fight club:
-- If the attacker is alive,  the attacker wins, else 
-- the defender wins:
fight attacker defender = if isAlive attacker then
                 attacker
              else
                 defender

-- I would expect the "fight" function to return a "robot".
-- But it does not:
*Main> victor = fight klaus peter
*Main> :t victor
victor :: ([Char] -> Integer -> Integer -> Bool) -> Bool

*Main> printRobot klaus
"Name: \"Klaus\", health: 50, attack: 5"
*Main> printRobot peter
"Name: \"Peter\", health: 60, attack: 7"
*Main> printRobot victor 

<interactive>:25:12: error:
    • Couldn't match type ‘[Char]’ with ‘Bool’
      Expected type: ([Char] -> Integer -> Integer -> [Char]) -> Bool
        Actual type: ([Char] -> Integer -> Integer -> Bool) -> Bool
    • In the first argument of ‘printRobot’, namely ‘victor’
      In the expression: printRobot victor
      In an equation for ‘it’: it = printRobot victor

问题

• 为什么签名是isAlive不是(t1 -> a -> t -> Bool) -> Bool ？
• 我的fight怎么了？功能？

到目前为止我学到了什么

以我目前的理解，我无法解决这个问题，但现在(感谢@chi的精彩回答)我可以理解这个问题。

对于所有其他陷入同样陷阱的初学者，这是我对问题的简化版本的推理:

• 我构建了一个包含两个字符串的闭包 s1 , s2和一个 int i1通过buildSSIclosure 。通过“发送消息”(传递函数)到闭包中，我可以访问闭包的“状态”。
• 我可以编写简单的访问器 getS1 , getS2 ，和getI1
• 我想编写一个采用 ssiClosure 的函数并获得 Int ，以及 [Char]通过访问器获取属性。

-- IMPORTANT: the return value `t` is not bound to a specific type
buildSSIclosure :: [Char] -> [Char] -> Int -> ([Char] -> [Char] -> Int -> t) -> t
buildSSIclosure s1 s2 i1 = (\message -> message s1 s2 i1)

buildSSIclosure的定义有t不受约束。当使用任何访问器时，t ssiClosure的实例绑定(bind)到一个类型:

getS1 :: (([Char] -> [Char] -> Int -> [Char]) -> [Char]) -> [Char]
getS2 :: (([Char] -> [Char] -> Int -> [Char]) -> [Char]) -> [Char]
getI1 :: (([Char] -> [Char] -> Int -> Int) -> Int) -> Int

-- `t` is bound to [Char]
getS1 ssiClosure = ssiClosure (\ s1 _ _ -> s1)

-- `t` is bound to [Char]
getS2 ssiClosure = ssiClosure (\ _ s2 _ -> s2)

-- `t` is bound to int
getI1 ssiClosure = ssiClosure (\ _ _ i1 -> i1)

我直接访问 lambda 函数调用的两个参数这有效并将绑定(bind) t至[Char] :

getS1I1_direct ssiClosure = ssiClosure (\ s1 _ i1 -> s1 ++ ", " ++ show i1)

调用两个字符串访问器

我可以访问 S1和S2通过访问器。这是有效的，因为 getS1 ，和getS2绑定(bind)t来自ssiClosure至[Char] :

getS1S2_indirect ssiClosure = show (getS1 ssiClosure) ++ ", " ++ show(getS2 ssiClosure)

访问 Char 和 Int

下一步是访问 int 和 string 属性。那甚至无法编译!

这是我的理解:

• 调用 getS1需求t从关闭到绑定(bind)到[Char]
• 调用 getI1需求t从关闭到绑定(bind)到Int

它不能同时绑定(bind)到两者，因此编译器告诉我:

getS1I1_indirect ssiClosure = show(getS1 ssiClosure) ++ ", "  ++ show(getI1 ssiClosure)

    • Couldn't match type ‘[Char]’ with ‘Int’
      Expected type: ([Char] -> [Char] -> Int -> Int) -> Int
        Actual type: ([Char] -> [Char] -> Int -> [Char]) -> [Char]
    • In the first argument of ‘getI1’, namely ‘ssiClosure’
      In the first argument of ‘show’, namely ‘(getI1 ssiClosure)’
      In the second argument of ‘(++)’, namely ‘show (getI1 ssiClosure)’

我仍然没有能力通过查看错误来识别问题。但还是有希望的;-)

Answer 1

Why is the signature of isAlive not (t1 -> a -> t -> Bool) -> Bool?

isAlive r = r (\_ health _ -> health > 0)

让我们从 lambda 开始。我想你可以看到这一点

(\_ health _ -> health > 0) :: a -> b -> c -> Bool

哪里b必须都是 Ord 类(对于 > )和 Num (对于0)

自从争论r以 lambda 作为输入，它必须是一个以 lambda 作为输入的函数:

r :: (a -> b -> c -> Bool) -> result

最后，isAlive需要r作为参数，并返回与 r 相同的结果。因此:

isAlive :: ((a -> b -> c -> Bool) -> result) -> result

添加约束并稍微重命名类型变量，我们得到 GHCi 的类型:

isAlive :: (Ord a, Num a) => ((t1 -> a -> t -> Bool) -> t2) -> t2

请注意，这种类型比以下类型更通用:

isAlive :: (Ord a, Num a) => ((t1 -> a -> t -> Bool) -> Bool) -> Bool

大致意思是“给我一个Bool生成机器人，我会给你一个Bool”。

What is wrong with my fight function?

fight attacker defender = if isAlive attacker then
                 attacker
              else
                 defender

这很棘手。上面的代码调用isAlive attacker这迫使 attacker输入 (a -> b -> c -> Bool) -> result 。然后，result必须是Bool因为它用在if中。此外，这使得defender具有与 attacker 相同的类型因为 if then else 的两个分支必须返回相同类型的值。

因此，输出 fight必须是“Bool-生成机器人”，即不再能够生成其他任何东西的机器人。

这可以使用 2 级类型来修复，但如果您是初学者，我不建议您现在尝试此操作。对于初学者来说，这个练习看起来相当高级，因为传递了很多 lambda。

从技术上讲，您在各处传递 Church 编码的元组，而这仅适用于 2 级多态性。传递一阶元组会简单得多。

无论如何，这里有一个可能的解决方案。这打印 Klaus作为获胜者。

{-# LANGUAGE Rank2Types #-}

isAlive :: (Ord h, Num h) => ((n -> h -> a -> Bool) -> Bool) -> Bool
isAlive r = r (\_ health _ -> health > 0)

-- A rank-2 polymorphic robot, isomorphic to (n, h, a)
type Robot n h a = forall result . (n -> h -> a -> result) -> result

fight :: (Ord h, Num h) => Robot n h a -> Robot n h a -> Robot n h a
fight attacker defender = if isAlive attacker
   then attacker
   else defender

robot :: n -> h -> a -> Robot n h a
robot name health attack = \message -> message name health attack

printRobot :: (Show n, Show h, Show a) => ((n -> h -> a -> String) -> String) -> String
printRobot r = r (\name health  attack -> 
   "Name: " ++ show name ++
   ", health: " ++ show health ++
   ", attack: " ++ show attack)

klaus, peter :: Robot String Int Int
klaus = robot "Klaus" 50 5
peter = robot "Peter" 60 7

main :: IO ()
main = do
   let victor = fight klaus peter
   putStrLn (printRobot victor)

最后一点

我建议您为每个顶级函数添加类型。虽然 Haskell 可以推断这些，但对于程序员来说，手头有类型是非常方便的。此外，如果您编写了您想要的类型，GHC 会检查它。经常发生 GHC 推断出程序员不希望的类型的情况，使代码看起来很好，但实际上并非如此。当推断的类型与代码的其余部分不匹配时，这通常会导致程序稍后出现令人费解的类型错误。