Haskell foldl 无法构造无限类型

Question

我正在阅读“Get Programming with Haskell”一书：https://www.manning.com/books/get-programming-with-haskell

有一节以函数式风格介绍OOP的课程，以战斗机器人为例：

robot (name,attack,hp)  = \message -> message (name,attack,hp)

killerRobot = robot ("Kill3r",25,200)
name (n,_,_) = n
attack (_,a,_) = a
hp (_,_,hp) = hp 

getName aRobot = aRobot name
getAttack aRobot = aRobot attack
getHP aRobot = aRobot hp


setName aRobot newName = aRobot (\(n,a,h) -> robot (newName,a,h))
setAttack aRobot newAttack = aRobot (\(n,a,h) -> robot (n,newAttack,h))
setHP aRobot newHP = aRobot (\(n,a,h) -> robot (n,a,newHP))

nicerRobot = setName killerRobot "kitty"
gentlerRobot = setAttack killerRobot 5
softerRobot = setHP killerRobot 50

printRobot aRobot = aRobot (\(n,a,h) -> n ++
                                        " attack:" ++ (show a) ++
                                        " hp:"++ (show h))
                                        
damage aRobot attackDamage = aRobot (\(n,a,h) ->
                                      robot (n,a,h-attackDamage))


fight aRobot defender = damage defender attack
  where attack = if (getHP aRobot) > 10
                 then getAttack aRobot
                 else 0

gentleGiant = robot ("Mr. Friendly", 10, 300)



gentleGiantRound1 = fight killerRobot gentleGiant
killerRobotRound1 = fight gentleGiant killerRobot
gentleGiantRound2 = fight killerRobotRound1 gentleGiantRound1
killerRobotRound2 = fight gentleGiantRound1 killerRobotRound1
gentleGiantRound3 = fight killerRobotRound2 gentleGiantRound2
killerRobotRound3 = fight gentleGiantRound2 killerRobotRound2


fastRobot = robot ("speedy", 15, 40)
slowRobot = robot ("slowpoke",20,30)

fastRobotRound3 = fight slowRobotRound3 fastRobotRound2
fastRobotRound2 = fight slowRobotRound2 fastRobotRound1
fastRobotRound1 = fight slowRobotRound1 fastRobot
slowRobotRound2 = fight fastRobotRound1 slowRobotRound1
slowRobotRound3 = fight fastRobotRound2 slowRobotRound2
slowRobotRound1 = fight fastRobot slowRobot

我看到代码底部的战斗示例必须创建新变量来存储每次战斗后创建的对象，因为每个对象实际上只是一个存储其状态的闭包，闭包需要绑定到东西。

我很好奇能不能用damage函数连续多次攻击一个机器人。之前的课介绍了高阶函数，包括foldl，所以我用它多次尝试破坏gentleGiant机器人：

pummeledGiant = foldl damage gentleGiant [100,50,100,500]

但我收到此错误：

    • Occurs check: cannot construct the infinite type:
        t1 ~ (([Char], Integer, Integer) -> t1) -> t1
      Expected type: ((([Char], Integer, Integer)
                       -> (([Char], Integer, Integer) -> t1) -> t1)
                      -> (([Char], Integer, Integer) -> t1) -> t1)
                     -> Integer
                     -> (([Char], Integer, Integer)
                         -> (([Char], Integer, Integer) -> t1) -> t1)
                     -> (([Char], Integer, Integer) -> t1)
                     -> t1
        Actual type: ((([Char], Integer, Integer)
                       -> (([Char], Integer, Integer) -> t1) -> t1)
                      -> (([Char], Integer, Integer)
                          -> (([Char], Integer, Integer) -> t1) -> t1)
                      -> (([Char], Integer, Integer) -> t1)
                      -> t1)
                     -> Integer
                     -> (([Char], Integer, Integer)
                         -> (([Char], Integer, Integer) -> t1) -> t1)
                     -> (([Char], Integer, Integer) -> t1)
                     -> t1
    • In the first argument of ‘foldl’, namely ‘damage’
      In the expression: foldl damage gentleGiant [100, 50, 100, 500]
      In an equation for ‘pummeledGiant’:
          pummeledGiant = foldl damage gentleGiant [100, 50, 100, ....]
    • Relevant bindings include
        pummeledGiant :: (([Char], Integer, Integer)
                          -> (([Char], Integer, Integer) -> t1) -> t1)
                         -> (([Char], Integer, Integer) -> t1) -> t1
          (bound at <interactive>:2:1)

我的理解是 foldl 有 3 个参数：

二元函数
初始值
值列表

并以左向方式逐步将二元函数应用于值对，从初始值和值列表中的第一个值开始，“链接”结果，例如：

foldl (+) 0 [1..3] = ((0 + 1) + 2) + 3

我不明白我遇到的错误，也看不出我的使用方式有任何逻辑问题 foldl。我做错了什么？

Answer 1

你的直觉是对的。关于如何使用 foldl，您的想法完全正确。唯一的问题是您用于机器人的类型比 Haskell 可以轻松处理的复杂得多。您可以使用 newtype 让事情安定下来，足以做到这一点。首先，这是原始代码的相关部分，其中包含类型签名和类型同义词：

{-# LANGUAGE RankNTypes #-}

type Robot = forall a. ((String, Integer, Integer) -> a) -> a

robot :: (String, Integer, Integer) -> Robot
robot (name,attack,hp)  = \message -> message (name,attack,hp)

damage :: Robot -> Integer -> Robot
damage aRobot attackDamage = aRobot (\(n,a,h) ->
                                      robot (n,a,h-attackDamage))

gentleGiant :: Robot
gentleGiant = robot ("Mr. Friendly", 10, 300)

pummeledGiant :: Robot
pummeledGiant = foldl damage gentleGiant [100,50,100,500]

(注意：我用的类型其实和推断的类型不一样，所以由此产生的错误会有点不同，但根本问题是一样的。)

看看Robot如何包含类型变量a？这意味着它是一个多态类型。通常，当你真正去使用一个多态类型时，Haskell可以弄清楚类型变量将是什么并填充它们，但是在damage的情况下，它不能（它是一个等级-2 型）。这意味着您随后将具有多态类型的 damage 放入也具有多态类型的 foldl 中。将一种多态类型置于另一种多态类型中需要非谓语类型，Haskell 尚不支持。

无论如何，要修复它，您可以使用 newtype 包装器，如下所示：

{-# LANGUAGE RankNTypes #-}

newtype Robot = MkRobot (forall a. ((String, Integer, Integer) -> a) -> a)

robot :: (String, Integer, Integer) -> Robot
robot (name,attack,hp)  = MkRobot $ \message -> message (name,attack,hp)

damage :: Robot -> Integer -> Robot
damage (MkRobot aRobot) attackDamage = aRobot (\(n,a,h) ->
                                      robot (n,a,h-attackDamage))

gentleGiant :: Robot
gentleGiant = robot ("Mr. Friendly", 10, 300)

pummeledGiant :: Robot
pummeledGiant = foldl damage gentleGiant [100,50,100,500]

不过，就我个人而言，初学者教程使用像这样的多态延续传递样式让我感到相当惊讶，这既是因为它比必要的更复杂，也是因为它会导致像这样的问题。我会设计完全不同的东西，像这样：

data Robot = Robot {
  name :: String,
  attack :: Integer,
  hp :: Integer
}

robot (n,a,h) = Robot n a h

killerRobot = robot ("Kill3r",25,200)

getName = name
getAttack = attack
getHP = hp

setName aRobot newName = aRobot{ name = newName }
setAttack aRobot newAttack = aRobot{ attack = newAttack }
setHP aRobot newHP = aRobot{ hp = newHP }

nicerRobot = setName killerRobot "kitty"
gentlerRobot = setAttack killerRobot 5
softerRobot = setHP killerRobot 50

printRobot (Robot n a h) = n ++
                           " attack:" ++ (show a) ++
                           " hp:"++ (show h)
                                        
damage (Robot n a h) attackDamage = Robot n a (h-attackDamage)


fight aRobot defender = damage defender attack
  where attack = if (getHP aRobot) > 10
                 then getAttack aRobot
                 else 0

gentleGiant = robot ("Mr. Friendly", 10, 300)



gentleGiantRound1 = fight killerRobot gentleGiant
killerRobotRound1 = fight gentleGiant killerRobot
gentleGiantRound2 = fight killerRobotRound1 gentleGiantRound1
killerRobotRound2 = fight gentleGiantRound1 killerRobotRound1
gentleGiantRound3 = fight killerRobotRound2 gentleGiantRound2
killerRobotRound3 = fight gentleGiantRound2 killerRobotRound2


fastRobot = robot ("speedy", 15, 40)
slowRobot = robot ("slowpoke",20,30)

fastRobotRound3 = fight slowRobotRound3 fastRobotRound2
fastRobotRound2 = fight slowRobotRound2 fastRobotRound1
fastRobotRound1 = fight slowRobotRound1 fastRobot
slowRobotRound2 = fight fastRobotRound1 slowRobotRound1
slowRobotRound3 = fight fastRobotRound2 slowRobotRound2
slowRobotRound1 = fight fastRobot slowRobot

pummeledGiant = foldl damage gentleGiant [100,50,100,500]

这更加地道Haskell。请注意，大部分代码仍然相同；它只是使用 data 制作的常规类型来存储机器人，而不是奇怪的 CPS 元组。

Haskell foldl 无法构造无限类型

Haskell foldl cannot construct the infinite type

haskell

types

fold