Haskell newbie on types

Question

I'm completely new to Haskell (and more generally to functional programming), so forgive me if this is really basic stuff. To get more than a taste, I try to implement in Haskell some algorithmic stuff I'm working on. I have a simple module Interval that implements intervals on the line. It contains the type

data Interval t = Interval t t

the helper function

makeInterval :: (Ord t) => t -> t -> Interval t  
makeInterval l r  | l <= r    = Interval l r  
                  | otherwise = error "bad interval"  

and some utility functions about intervals.

Here, my interest lies in multidimensional intervals (d-intervals), those objects that are composed of d intervals. I want to separately consider d-intervals that are the union of d disjoint intervals on the line (multiple interval) from those that are the union of d interval on d separate lines (track interval). With distinct algorithmic treatments in mind, I think it would be nice to have two distinct types (even if both are lists of intervals here) such as

import qualified Interval as I

-- Multilple interval  
newtype MInterval t = MInterval [I.Interval t]  

   -- Track interval  
newtype TInterval t = TInterval [I.Interval t]    

to allow for distinct sanity checks, e.g.

makeMInterval :: (Ord t) => [I.Interval t] -> MInterval t
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)]  
                   then (MInterval is)
                   else error "bad multiple interval"


makeTInterval :: (Ord t) => [I.Interval t] -> TInterval t
makeTInterval  = TInterval 

I now get to the point, at last! But some functions are naturally concerned with both multiple intervals and track intervals. For example, a function order would return the number of intervals in a multiple interval or a track interval. What can I do? Adding

-- Dimensional interval
data DInterval t = MIntervalStuff (MInterval t) | TIntervalStuff (TInterval t)

does not help much, since, if I understand well (correct me if I'm wrong), I would have to write

order :: DInterval t -> Int
order (MIntervalStuff (MInterval is)) = length is
order (TIntervalStuff (TInterval is)) = length is

and call order as order (MIntervalStuff is) or order (TIntervalStuff is) when is is a MInterval or a TInterval. Not that great, it looks odd. Neither I want to duplicate the function (I have many functions that are concerned with both multiple and track intevals, and some other d-interval definitions such as equal length multiple and track intervals).

I'm left with the feeling that I'm completely wrong and have missed some important point about types in Haskell (and/or can't forget enough here about OO programming). So, quite a newbie question, what would be the best way in Haskell to deal with such a situation? Do I have to forget about introducing MInterval and TInterval and go with one type only?

Thanks a lot for your help,

Garulfo

Answer 1

Edit: this is the same idea as sclv's answer; his links provide more information on this technique.

What about this approach?

data MInterval = MInterval --multiple interval
data TInterval = TInterval --track interval

data DInterval s t = DInterval [I.Interval t]

makeMInterval :: (Ord t) => [I.Interval t] -> Maybe (DInterval MInterval t)
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)]
  then Just (DInterval is)
  else Nothing

order :: DInterval s t -> Int
order (DInterval is) = length is

equalOrder :: DInterval s1 t -> DInterval s2 t -> Bool
equalOrder i1 i2 = order i1 == order i2

addToMInterval :: DInterval MInterval t -> Interval t -> Maybe (DInterval MInterval t)
addToMInterval = ..

Here the type DInterval represents multi-dimension intervals, but it takes an extra type parameter as a phantom type. This extra type information allows the typechecker to differentiate between different kinds of intervals even though they have exactly the same representation.

You get the type safety of your original design, but all your structures share the same implementation. Crucially, when the type of the interval doesn't matter, you can leave it unspecified.

I also changed the implementation of your makeMInterval function; returning a Maybe for a function like this is much more idiomatic than calling error.

More explanation on Maybe:

Let's examine your function makeInterval. This function is supposed to take a list of Interval's, and if they meet the criteria return a multiple interval, otherwise a track interval. This explanation leads to the type:

makeInterval :: (Ord t) =>
  [I.Interval t] ->
  Either (DInterval TInterval t) (DInterval MInterval t)

Now that we have the type, how can we implement it? We'd like to re-use our makeMInterval function.

makeInterval is = maybe
                   (Left $ DInterval TInterval is)
                   Right
                   (makeMInterval is)

The function maybe takes three arguments: a default b to use if the Maybe is Nothing, a function a -> b if the Maybe is Just a, and a Maybe a. It returns either the default or the result of applying the function to the Maybe value.

Our default is the track interval, so we create a Left track interval for the first argument. If the maybe is Just (DInterval MInterval t), the multiple interval already exists so all that's necessary is to stick it into the Right side of the either. Finally, makeMInterval is used to create the multiple interval.

Answer 2

What you want are types with the same structure and common operations, but which may be distinguished, and for which certain operations only make sense on one or another type. The idiom for this in Haskell is Phantom Types.

1. http://www.haskell.org/haskellwiki/Phantom_type
2. http://www.haskell.org/haskellwiki/Wrapper_types
3. http://blog.malde.org/index.php/2009/05/14/using-a-phantom-type-to-label-different-kinds-of-sequences/
4. http://neilmitchell.blogspot.com/2007/04/phantom-types-for-real-problems.html