4 ms·
Heterogenous lists are always coming up when people try to translate OO ideas into Haskell. It's great that this example used the barrier of heterogeneity as a
by tel 13y ago
Heterogenous lists are always coming up when people try to translate OO ideas into Haskell. It's great that this example used the barrier of heterogeneity as a reason to think harder about their design instead of barreling forward.
In particular, heterogeneity causes a form of information loss via type erasure (existential typing). The problem is that this is pretty heavy machinery and is not always well-suited to such a simple problem as a heterogenous list. Additionally, once you've produced a type like
[forall a . Renderable a => a] -- not a valid Hs type, but close
frequently you've reduced your options for what to do down to really just a single choice. In this case, `render`. This is what's sometimes called the Existential Antipattern—if you have an existential type where only one way forward remains... you may as well just take that way forward. This is especially easy in a lazy language like Haskell.
renderEm :: Ball -> Player -> Player -> [IO ()] -- homogenous!
renderEm b p1 p2 = [render b, render p1, render p2]
Note that this is functionally very similar to the implementation of `render` for Game as given in the article. In particular, the only difference is that the article's `render` method destroys the barriers between these `IO` actions by sequencing:
instance Render Game where
render (Game b p1 p2) = sequence (renderEm b p1 p2)
where `sequence` sequences a list of monadic actions
-- try thinking about this as "distributing" a monad over a list
-- much like you distribute multiplication over addition
--
-- x (a + b) --> x a + x b
--
-- and then go look up Data.Traversable
sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) = ma >> sequence mas
This tension between a "reified list of actions" and a composite action is pretty much the heart of the expression problem—the reified list is an initial encoding and the final action the final encoding. This kind of thing shows up all the time when dealing with heterogenous lists. The reason being that OO basically favors final encodings to the extinction of initial ones... but initial encodings are what generate type information.
- deleted 13y ago[deleted]
- dllthomas 13y ago"[I]f you have an existential type where only one way forward remains... you may as well just take that way forward. This is especially easy in a lazy language like Haskell." This doesn't seem especially easy in Haskell (in that it doesn't seem harder elsewhere), but especially the case a lazy language like Haskell. In an eager language, (forall a . Renderable a => a) is isomorphic to (() -> IO ()) and subtly distinct from (IO ()).
- rntz 13y agoCould you explain what you mean here by initial/final encoding, and why you say OO favors final encodings but initial encodings generate type information? I'm familiar with the notions of initial algebra, and slightly less so with final coalgebras, but I don't quite see what you're getting at.
- tel 13y agoI'm running pretty fast and loose here, but you can see objects as being ADTs defined by their eliminators [0] while constructors produce new forms and their relevant type information. Eliminators can do that as well (in negative positions), but I want to drive home that a lot of what feels weird about Haskell comes from the effects of working with constructors/pattern matching. A similar comparison might be made between case classes and "regular" classes in Scala, but I don't know Scala as well. [0] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/adt.pdf http://www.cs.ox.ac.uk/jeremy.gibbons/publications/adt.pdf