Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to correct my OOP tendencies when programming in Haskell

I have this recurrent problem when programming in Haskell. At some point, I try to simulate an OOP approach. Here I was writing some sort of AI for a flash game I found, and I'd like to describe the various pieces and the level as a list of pieces.

module Main where

type Dimension = (Int, Int)
type Position = (Int, Int)
data Orientation = OrienLeft | OrienRight

data Pipe = Vertical | Horizontal | UpLeft | UpRight | DownLeft | DownRight
data Tank = Tank Dimension Orientation
data Bowl = Bowl Dimension
data Cross = Cross
data Source = Source Dimension

-- desired
-- data Piece = Pipe | Tank | Bowl | Cross | Source

-- So that I can put them in a list, and define
-- data Level = [Piece]

I know I should abstract the functionalities and put Them in a list, but I often feel blocked in the process of writing code. What is the general mindset I should have in these situations?

like image 890
meditans Avatar asked Sep 18 '13 08:09

meditans


1 Answers

You're on your way to some great code. Let me push it a few more steps toward a Haskell-like solution.

You've successfully modeled each Piece as an independent entity. This looks completely fine as is, but you want to be able to work with collections of pieces. The most immediate way to do this is to describe a type which can be any of the pieces desired.

data Piece = PipePiece   Pipe
           | TankPiece   Tank
           | BowlPiece   Bowl
           | CrossPiece  Cross
           | SourcePiece Source

which would let you write a list of pieces like

type Kit = [Piece]

but requires that when you consume your Kit that you pattern match on the different kinds of Pieces

instance Show Piece where
  show (PipePiece   Pipe)   = "Pipe"
  show (TankPiece   Tank)   = "Tank"
  show (BowlPiece   Bowl)   = "Bowl"
  show (CrossPiece  Cross)  = "Cross"
  show (SourcePiece Source) = "Source"

showKit :: Kit -> String 
showKit = concat . map show

There's also a strong argument for reducing the complexity of the Piece type by "flattening" out some redundant information

type Dimension   = (Int, Int)
type Position    = (Int, Int)
data Orientation = OrienLeft | OrienRight
data Direction   = Vertical | Horizontal | UpLeft | UpRight | DownLeft | DownRight

data Piece = Pipe Direction
           | Tank Dimension Orientation
           | Bowl Dimension
           | Cross
           | Source Dimension

which eliminates many redundant type constructors at the expense of no longer being able to reflect what kind of piece you have in the type of a function—no longer can we write

rotateBowl :: Bowl -> Bowl
rotateBowl (Bowl orientation) = Bowl (rotate orientation)

but instead

rotateBowl :: Piece -> Piece
rotateBowl (Bowl orientation) = Bowl (rotate orientation)
rotateBowl somethingElse      = somethingElse

which is pretty annoying.

Hopefully that highlights some of the tradeoffs between those two models. There's at least one "more exotic" solution which uses type classes and ExistentialQuantification to "forget" about everything besides an interface. This is worth exploring as it's pretty tempting to do but is considered to be a Haskell anti-pattern. I'll describe it first then talk about the better solution.

To use ExistentialQuantification we remove the sum type Piece and create a type class for pieces.

{-# LANGUAGE ExistentialQuantification #-}

class Piece p where
  melt :: p -> ScrapMetal

instance Piece Pipe
instance Piece Bowl
instance ...

data SomePiece = forall p . Piece p => SomePiece p

instance Piece SomePiece where
  melt (SomePiece p) = melt p

forgetPiece :: Piece p => p -> SomePiece
forgetPiece = SomePiece

type Kit = [SomePiece]

meltKit :: Kit -> SomePiece
meltKit = combineScraps . map melt

This is an antipattern because ExistentialQuantification leads to more complex type errors and the erasure of lots of interesting information. The usual argument goes that if you're going to erase all information besides the ability to melt the Piece, you ought to have just melted it to begin with.

myScrapMetal :: [ScrapMetal]
myScrapMetal = [melt Cross, melt Source Vertical]

And if your typeclass has multiple functions then perhaps your real functionality is stored in that class. For instance, let's say we can melt a piece and also sell it, perhaps the better abstraction would be the following

data Piece = { melt :: ScrapMetal
             , sell :: Int
             }

pipe :: Direction -> Piece
pipe _ = Piece someScrap 2.50

myKit :: [Piece]
myKit = [pipe UpLeft, pipe UpRight]

In all honesty, this is almost exactly what you're getting via the ExistentialQuantification method, but much more directly. When you erase the type information via forgetPiece you leave only the typeclass dictionary for class Piece---this is exactly a product of the functions in the typeclass which is what we're explicitly modeling with the data Piece type just described.


The one reason I can think of to use ExistentialQuantification is best exemplified by Haskell's Exception system—if you're interested, take a look at how it's implemented. The short of it being that Exception had to be designed such that anyone could add a new Exception in any code and have it be routable through the shared Control.Exception machinery while maintaining enough identity for the user to catch it as well. This required the Typeable machinery as well... but it's almost certainly overkill.


The takeaway should be that the model you use will depend a lot on how you end up consuming your data type. Initial encodings where you represent everything as an abstract ADT like the data Piece solution are nice in that they throw away little information... but can also be both unwieldy and slow. Final encodings like the melt/sell dictionary are often more efficient, but require deeper knowledge about what a Piece "means" and how it will be used.

like image 191
J. Abrahamson Avatar answered Oct 03 '22 10:10

J. Abrahamson