The Universe of Discourse

How do I keep type constructors from overrunning my Haskell program?

Here's a little function I wrote over the weekend as part of a suite for investigating Yahtzee:

  type DiceChoice = [ Bool ]
  type DiceVals   = [ Integer ]
  type DiceState = (DiceVals, Integer)

  allRolls :: DiceChoice -> DiceState -> [ DiceState ]
  allRolls [] ([], n) = [ ([], n-1) ]
  allRolls [] _ = undefined

  allRolls (chosen:choices) (v:vs, n) =
      allRolls choices (vs,n-1) >>=
          \(roll,_) -> [ (d:roll,  n-1) | d <- rollList ]
            where rollList = if chosen then [v] else [ 1..6 ]       

I don't claim this code is any good; I was just hacking around exploring the problem space. But it does do what I wanted.

The allRolls function takes a current game state, something like

    ( [ 6, 4, 4, 3, 1 ], 2 )

which means that we have two rolls remaining in the round, and the most recent roll of the five dice showed 6, 4, 4, 3, and 1, respectively. It also takes a choice of which dice to keep: The list

    [ False, True, True, False, False ]

means to keep the 4's and reroll the 6, the 3, and the 1. The allRolls function then produces a list of the possible resulting dice states, in this case 216 items:

   [ ( [ 1, 4, 4, 1, 1 ], 1 ) ,
     ( [ 1, 4, 4, 1, 2 ], 1 ) ,
     ( [ 1, 4, 4, 1, 3 ], 1 ) ,
     …
     ( [ 6, 4, 4, 6, 6 ], 1 ) ]

This function was not hard to write and it did work adequately.

But I wasn't satisfied. What if I have some unrelated integer list and I pass it to a function that is expecting a DiceVals, or vice versa? Haskell type checking is supposed to prevent this from happening, and by using type aliases I am forgoing this advantage. No problem, I can easily make DiceVals and the others into datatypes:

    data DiceChoice = DiceChoice [ Bool ]
    data DiceVals   = DiceVals [ Integer ]
    data DiceState = DiceState (DiceVals, Integer)

The declared type of allRolls is the same:

    allRolls :: DiceChoice -> DiceState -> [ DiceState ]

But now I need to rewrite allRolls, and a straightforward translation is unreadable:

    allRolls (DiceChoice []) (DiceState (DiceVals [], n)) = [ DiceState(DiceVals [], n-1) ]
    allRolls (DiceChoice []) _ = undefined
    allRolls (DiceChoice (chosen:choices)) (DiceState (DiceVals (v:vs), n)) =
        allRolls (DiceChoice choices) (DiceState (DiceVals vs,n-1)) >>=
            \(DiceState(DiceVals roll, _)) -> [ DiceState (DiceVals (d:roll), n-1) | d <- rollList ]
              where rollList = if chosen then [v] else [ 1..6 ]

This still compiles and it still produces the results I want. And it has the type checking I want. I can no longer pass a raw integer list, or any other isomorphic type, to allRolls. But it's unmaintainable.

I could rename allRolls to something similar, say allRolls__, and then have allRolls itself be just a type-checking front end to allRolls__, say like this:

    allRolls :: DiceChoice -> DiceState -> [ DiceState ]                             
    allRolls (DiceChoice dc) (DiceState ((DiceVals dv), n)) =                        
        allRolls__ dc dv n                                                             

    allRolls__ [] [] n = [ DiceState (DiceVals [], n-1) ]                            
    allRolls__ [] _  _ = undefined                                                   
    allRolls__ (chosen:choices) (v:vs) n =                                           
        allRolls__ choices vs n   >>=                                                  
            \(DiceState(DiceVals roll,_)) -> [ DiceState (DiceVals (d:roll), n-1) | d <- rollList ]
              where rollList = if chosen then [v] else [ 1..6 ]            

And I can do something similar on the output side also:

    allRolls :: DiceChoice -> DiceState -> [ DiceState ]                             
    allRolls (DiceChoice dc) (DiceState ((DiceVals dv), n)) =                        
        map wrap $ allRolls__ dc dv n                                                  
          where wrap (dv, n) = DiceState (DiceVals dv, n)                              

    allRolls__ [] [] n = [ ([], n-1) ]                                               
    allRolls__ [] _  _ = undefined                                                   

    allRolls__ (chosen:choices) (v:vs) n =                                           
        allRolls__ choices vs n   >>=                                                  
            \(roll,_) -> [ (d:roll, n-1) | d <- rollList ]                               
              where rollList = if chosen then [v] else [ 1..6 ]   

This is not unreasonably longer or more cluttered than the original code. It does forgo type checking inside of allRolls__, unfortunately. (Suppose that the choices and vs arguments had the same type, and imagine that in the recursive call I put them in the wrong order.)

Is this considered The Thing To Do? And if so, where could I have learned this, so that I wouldn't have had to invent it? (Or, if not, where could I have learned whatever is The Thing To Do?)

I find most Haskell instruction on the Internet to be either too elementary

pet the nice monad, don't be scared, just approach it very slowly and it won't bite

or too advanced

here we've enabled the {-# SemispatulatedTypes #-} pragma so we can introduce an overloaded contravariant quasimorphism in the slice category

with very little practical advice about how to write, you know, an actual program. Where can I find some?

[Other articles in category /prog/haskell] permanent link