Haskell foldl cannot construct the infinite type

user_11872389 0
Viewed 88

I'm working through the book "Get Programming with Haskell": https://www.manning.com/books/get-programming-with-haskell

There is a lesson introducing OOP in a functional style, using fighting robots as an example:

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

I saw how the example fights at the bottom of the code had to create new variables to store objects created after each fight, since each object is really just a closure that stores its state and the closure needs to be bound to something.

I was curious to see if I could attack a robot many times in succession using the damage function. The lesson before this introduced higher order functions, including foldl, so I tried to damage the gentleGiant robot multiple times using it:

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

but I get this error:

    • 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)

My understanding is that foldl takes 3 arguments:

  1. a binary function
  2. an initial value
  3. a list of values

and progressively applies the binary function to pairs of values in a left-wise manner, starting with the initial value and the first value in the list of values, "chaining" the result, e.g.:

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

I don't understand the error that I encountered and can't see any logical issue with how I used foldl. What have I done wrong?

fold haskell types
1 Answers

Your intuition is right. You have exactly the right idea for how to use foldl. The only problem is that the type you're using for robots is more complicated than Haskell can easily handle. You can use a newtype to make things settle down enough to do that. First, here's the relevant bits of your original code, with type signatures and a type synonym thrown in:

{-# 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]

(Note: The type I used is actually different than the one that was inferred, so the errors from this will be a little bit different, but the root problem is the same.)

See how Robot contains a type variable a? That means it's a polymorphic type. Usually, when you actually go to use a polymorphic type, Haskell can figure out what the type variables will be and fill them in, but in the case of damage, it can't (it's a rank-2 type). That means you're then putting damage, which has a polymorphic type, into foldl, which also has a polymorphic type. Putting one polymorphic type inside of another requires impredicative types, which Haskell doesn't yet support well.

Anyway, to fix it, you can use a newtype wrapper, like this:

{-# 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]

Personally, though, I'm rather surprised that a beginner tutorial is using polymorphic continuation-passing style like this, both because it's more complicated than necessary and because it causes problems like this one. I would have designed things completely differently, like this:

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]

That's much more idiomatic Haskell. Note that most of the code is still the same; it just uses a regular type made with data to store the robots, instead of the weird CPS tuple.

user_75090650
Related