How to avoid ugly code resolving this problem in Haskell (LANGUAGE extentions)?

Question

I'm trying to write a program that simulates several creatures in a world. Basically the word sends a message over a list of creatures, and each creature gives his response, which in turn modifies the world.

I simplified what I'm trying to write in the following skeleton:

module Structure0 where
type Message = String
class Creature a where
    processInput :: a -> Message -> Message
class World a where
    processAction :: a -> b -> Message -> a
    getCreatures  :: a -> [b]

---- USAGE EXAMPLE ----
data Parrot = Parrot Int deriving Show
instance Creature Parrot where
    processInput p s = s
data ParrotWorld = ParrotWorld [Parrot]
instance World ParrotWorld where
    processAction w p s = w
    getCreatures (ParrotWorld ps) = ps

In this code, I would that the parameter b in World class definition could assume all the data value that belong to the Creature class, something like:

processAction :: (Creature b) => a -> b -> Message -> a

Of course this examples aren't actual haskell code, lo let's pass illustrating two solution i found: the first, involving ExistentialQuantification:

{-# LANGUAGE ExistentialQuantification #-}
module Structure1 where
type Message = String
class Creature_ a where
    processInput :: a -> Message -> Message
data Creature = forall c. Creature_ c => Creature c
instance Creature_ Creature where
    processInput (Creature c) = processInput c
class World a where
    processAction :: a -> Creature -> Message -> a
    getCreatures  :: a -> [Creature]

---- USAGE EXAMPLE ----
data Parrot = Parrot Int deriving Show
instance Creature_ Parrot where
    processInput u s = s
data ParrotWorld = ParrotWorld [Creature]
instance World ParrotWorld where
    processAction w p s = w
    getCreatures (ParrotWorld ps) = ps

and the second, suggested by a kind guy on #haskell, using TypeFamilies:

{-# LANGUAGE TypeFamilies, FlexibleContexts #-}
module Structure2 where
type Message = String
class Creature a where
    processInput :: a -> Message -> Message
class (Creature (WorldCreature a)) => World a where
    type WorldCreature a :: *
    processAction :: a -> WorldCreature a -> Message -> a
    getCreatures  :: a -> [WorldCreature a]
---- USAGE EXAMPLE ----
data Parrot = Parrot Int deriving Show
instance Creature Parrot where
    processInput p s = s
data ParrotWorld = ParrotWorld [Parrot]
instance World ParrotWorld where
    type WorldCreature ParrotWorld = Parrot
    processAction w p s = w
    getCreatures (ParrotWorld ps) = ps

The main objective of this exercise is writing nice, elegant code. So, the questions:

1) Should I express Creature as a Class instead of a Data? (I'm doing this because a Creature is just a thing that implement the processInput function, and the many actual Creature implementations vary a lot; expecially during prototyping, I'd like not to change constantly the way in which a Creature pattern-matches.

2) The first solution I provide it's a bit ugly due to the boilerplate of maintaing both Creature and Creature_ versions. It has the benefit, however, that I can write mixed list of type [Creature]; Problem is that I can't pattern match against an object, id est things like:

\(Creature (Parrot x)) -> x

will fail due to type system. Can I make this all right?

3) The second solution has a problem of extendibility: say I would to construct a World with two types of creatures, say Parrot1 and Parrot2: how could I write the code in that case?

4) Am I structuring the code from a wrong point of view? Can I get an elegant solution just using plain haskell?

Thank you all :)

Carlo

Answer 1

1 class vs. data

Creature should be a class -- it describes an interface. Data should be used when you think of actually communicating values, or when you need to introduce a new type, wrapping an existing object with new behavior. For example, the Identity monad needs to wrap its values in a new type, or else you'd see instance Monad a for all a, which would cause conflicts with making anything else a Monad instance. But, you may need to wrap it.

2 lists

There is a way to do it with Data.Dynamic, but every time I've thought about doing it that way, I've been able to think of a way to do it with regular typeclasses instead. That said, I haven't written that much Haskell, and many libraries certainly rely on Data.Dynamic. If you want to really unbox a type, then you probably need to use it.

3 extensionality

As before, if you can leave type-specific functionality in the classes, that is best. It'd be most helpful if you could post an example, showing why you can't add another function to Creature. I'll assume you want to count numParrots in the example below, and you really do need to unbox them.

4 general comments

There are always many solutions to a problem. Based on your description, I'd think that "different worlds should entail different types of messages", not that a world should be tied to a specific type of creature (e.g. ParrotWorld).

another solution

here's my solution, using Data.Typeable. As mentioned above, it's my first time using it, so there may be a cleaner way.

{-# LANGUAGE DeriveDataTypeable,
             ImpredicativeTypes,
             NoMonomorphismRestriction,
             RankNTypes,
             ScopedTypeVariables #-}

module Test where

import Data.Typeable

type Message = String

class Typeable α => Creature α where
    processInput :: α -> Message -> Message

-- box a creature
type BoxedC = (Message -> Message, Typeable β => Maybe β)
boxC :: Creature α => α -> BoxedC
boxC x = (processInput x, cast x)

class World α where
    -- from your description, I'd not have Creature as part of this.
    processAction :: α -> Message -> α
    getCreatures :: α -> [BoxedC]

data Parrot = Parrot { parrotMessage :: String } deriving Typeable
data Lizard = Lizard { lizardMessage :: String } deriving Typeable

instance Creature Parrot where processInput p _ = (parrotMessage p)
instance Creature Lizard where processInput l _ = (lizardMessage l)

-- NOTE: Keep it simple and use a single World instance
-- (i.e. no typeclass) unless you need it.
data BaseWorld = BaseWorld { creatureList :: [BoxedC] }
instance World BaseWorld where
    processAction w _ = w
    getCreatures = creatureList

w = BaseWorld [boxC $ Parrot "parrot1", boxC $ Lizard "Lizard1"]

numParrots :: [BoxedC] -> Int
numParrots lst = foldl (+) 0 (map (go . snd) lst) where
    go :: (forall β. Typeable β => Maybe β) -> Int
    go (Just x :: Maybe Parrot) = 1
    go _ = 0

test = numParrots (getCreatures w)

The idea is similar to yours: we box creatures before we put them in a list. The boxed elements have enough data so that you can unbox the type if you need to. One final thing to mention, though it's maybe not what you want here, is that closures are powerful. You don't need to keep a list of creatures if you can express their results as function composition. For example, in pseudocode, you could have a function

bind_creature :: Creature -> World -> World

which adds a creature to a world, and World has a type which returns its next iteration,

data World = World { nextWorld :: World }

which you set to itself for the base, namely w = World w. For simplicity, let's assume that each creature has a function

transformWorld :: Creature -> World -> World

then you could implement bind_creature like,

bind_creature c w = World { nextWorld = transformWorld c (nextWorld w) }

hope it helps.