Personal tools

Haskell Quiz/Constraint Processing/Solution Jethr0

From HaskellWiki

< Haskell Quiz | Constraint Processing(Difference between revisions)
Jump to: navigation, search
m
 
m
Line 27: Line 27:
 
,("a:",1,"b:",3,"c:",4)]
 
,("a:",1,"b:",3,"c:",4)]
 
-}
 
-}
  +
</haskell>
  +
  +
  +
Obviously, solving a problem with built-in functionality always feels a little like cheating, because it's "pure chance" that the solution to the problem is already built-in.
  +
  +
So, for the sake of argument and because I was bored here's the same solution under the premise that haskell's List Monad didn't already exist.
  +
  +
Unfortunately I "had" to reimplement a fair bit of the Prelude, but that's what happens if you start creating unrealistic scenarios :). Of course, the "do" notation is also kind of a built-in, but representing it with bind (>>=) only made is less nice to look at.
  +
  +
<haskell>
  +
data List a = List a (List a) | Empty deriving (Show)
  +
  +
appendL :: List a -> List a -> List a
  +
appendL Empty ys = ys
  +
appendL (List x xs) ys = x `List` appendL xs ys
  +
  +
foldrL :: (a->b->b) -> b -> List a -> b
  +
foldrL _ start Empty = start
  +
foldrL f start (List x xs) = f x (foldrL f start xs)
  +
  +
concatL :: List (List a) -> List a
  +
concatL = foldrL appendL Empty
  +
  +
instance Functor List where
  +
fmap f xs = foldrL (\a b -> f a `List` b) Empty xs
  +
  +
instance Monad List where
  +
return x = List x Empty
  +
l >>= f = concatL . fmap f $ l
  +
  +
instance MonadPlus List where
  +
mzero = Empty
  +
mplus = appendL
  +
  +
range :: (Integral a) => a -> a -> List a
  +
range from to | from > to = Empty
  +
| from == to = List to Empty
  +
| otherwise = List from (range (from+1) to)
  +
  +
constr' = do a <- range 0 4
  +
b <- range 0 4
  +
c <- range 0 4
  +
guard (a < b)
  +
guard (a + b == c)
  +
return (a,b,c)
 
</haskell>
 
</haskell>

Revision as of 12:13, 19 December 2006


Basically there's nothing to be done in haskell for this quiz.

As the List Monad already provides non-deterministic evaluation with "guard" as a description of constraints, you really just have to write the problem in the List Monad and be done with it.

Of course one could write all kinds of wrapping hackery, but I think from the standpoint of usability and conciseness the built-in behaviour of haskell is already pretty optimal.


constr = do a <- [0..4]
            b <- [0..4]
            c <- [0..4]
            guard (a < b)
            guard (a + b == c)
            return ("a:",a,"b:",b,"c:",c)
 
{- 
> constr
[("a:",0,"b:",1,"c:",1)
,("a:",0,"b:",2,"c:",2)
,("a:",0,"b:",3,"c:",3)
,("a:",0,"b:",4,"c:",4)
,("a:",1,"b:",2,"c:",3)
,("a:",1,"b:",3,"c:",4)]
-}


Obviously, solving a problem with built-in functionality always feels a little like cheating, because it's "pure chance" that the solution to the problem is already built-in.

So, for the sake of argument and because I was bored here's the same solution under the premise that haskell's List Monad didn't already exist.

Unfortunately I "had" to reimplement a fair bit of the Prelude, but that's what happens if you start creating unrealistic scenarios :). Of course, the "do" notation is also kind of a built-in, but representing it with bind (>>=) only made is less nice to look at.

data List a = List a (List a) | Empty deriving (Show)
 
appendL :: List a -> List a -> List a
appendL Empty       ys    = ys
appendL (List x xs) ys    = x `List` appendL xs ys
 
foldrL :: (a->b->b) -> b -> List a -> b
foldrL _ start Empty       = start
foldrL f start (List x xs) = f x (foldrL f start xs)
 
concatL :: List (List a) -> List a
concatL = foldrL appendL Empty
 
instance Functor List where
    fmap f xs = foldrL (\a b -> f a `List` b) Empty xs
 
instance Monad List where
    return x = List x Empty
    l >>= f  = concatL . fmap f $ l
 
instance MonadPlus List where
    mzero = Empty
    mplus = appendL
 
range :: (Integral a) => a -> a -> List a
range from to | from > to  = Empty
              | from == to = List to Empty
              | otherwise  = List from (range (from+1) to)
 
constr' = do a <- range 0 4
             b <- range 0 4
             c <- range 0 4
             guard (a < b)
             guard (a + b == c)
             return (a,b,c)