January 2007 - Haskell-Cafe

Monad Set via GADT
by Roberto Zunino 12 Jan '07

12 Jan '07

To improve my understanding of GADT, I tried to define a Set datatype, with the usual operations, so that it can be made a member of the standard Monad class. Here I report on my experiments. First, I recap the problem. Data.Set.Set can not be made a Monad because of the Ord constraint on its parameter, while e.g. (return :: a -> m a) allows any type inside the monad m. This problem can be solved using an alternative monad class (restricted monad) so that the Ord context is actually provided for the monad operations. Rather, I aimed for the standard Monad typeclass. To avoid reinventing Data.Set.Set, my datatype is based on that. Basically, when we know of an Ord context, we use a Set. Otherwise, we use a simple list representation. Using a list is just enough to allow the implementation of return (i.e. (:[])) and (>>=) (i.e. map and (++)), so while not being very efficient, it is simple. Other non-monadic operators require an Ord context, so that we can turn lists into Set. My first shot at this was: data SetM a where L :: [a] -> SetM a SM :: Ord a => Set.Set a -> SetM a However, this was not enough to convince the type checker to use the Ord context stored in SM. Specifically, performing union with union (SM m1) (SM m2) = SM (m1 `Set.union` m2) causes GHC to report "No instance for (Ord a)". After some experiments, I found the following, using a type equality witness: data Teq a b where Teq :: Teq a a data SetM a where L :: [a] -> SetM a SM :: Ord w => Teq a w -> Set.Set w -> SetM a Now if I use union (SM p1 m1) (SM p2 m2) = case (p1,p2) of (Teq,Teq) -> SM Teq (m1 `Set.union` m2) it typechecks! This rises some questions I cannot answer: 1) Why the first version did not typececk? 2) Why the second one does? 3) If I replace (Teq a w) with (Teq w a), as in SM :: Ord w => Teq w a -> Set.Set w -> SetM a then union above does not typecheck! Why? I guess the type variable unification deriving from matching Teq is not symmetric as I expect it to be... Below, I attach the working version. Monad and MonadPlus instances are provided for SetM. Conversions from/to Set are also provided, requiring an Ord context. "Efficient" return and mzero are included, forcing the Set representation to be used, and requiring Ord (these could also be derived from fromSet/toSet, however). Comments are very welcome, of course, as well as non-GADT related alternative approaches. Regards, Roberto Zunino. ============================================================ \begin{code} {-# OPTIONS_GHC -Wall -fglasgow-exts #-} module SetMonad ( SetM() , toSet, fromSet , union, unions , return', mzero' ) where import qualified Data.Set as S import Data.List hiding (union) import Control.Monad -- Type equality witness data Teq a b where Teq :: Teq a a -- Either a list or a real Set data SetM a where L :: [a] -> SetM a SM :: Ord w => Teq a w -> S.Set w -> SetM a instance Monad SetM where return = L . (:[]) m >>= f = case m of L l -> unions (map f l) SM Teq s -> unions (map f (S.toList s)) instance MonadPlus SetM where mzero = L [] mplus = union -- Efficient variants for Ord types return' :: Ord a => a -> SetM a return' = SM Teq . S.singleton mzero' :: Ord a => SetM a mzero' = SM Teq S.empty -- Set union: use the best representation union :: SetM a -> SetM a -> SetM a union (L l1) (L l2) = L (l1 ++ l2) union (SM p1 m1) (SM p2 m2) = case (p1,p2) of (Teq,Teq) -> SM Teq (m1 `S.union` m2) union (L l1) (SM p m2) = case p of Teq -> SM Teq (m2 `S.union` S.fromList l1) union s1 s2 = union s2 s1 -- Try to put a SM first before folding, to improve performance unions :: [SetM a] -> SetM a unions = let isSM (SM _ _) = True isSM _ = False in foldl' union (L []) . uncurry (++) . break isSM -- Conversion from/to Set requires Ord toSet :: Ord a => SetM a -> S.Set a toSet (L l) = S.fromList l toSet (SM p m) = case p of Teq -> m fromSet :: Ord a => S.Set a -> SetM a fromSet = SM Teq -- Tests test :: IO () test = do let l = [1..3] :: [Int] s = fromSet (S.fromList l) g x = return' x `mplus` return' (x+100) print $ S.toList $ toSet $ do x <- s y <- s return' (x+y) -- [2,3,4,5,6] print $ S.toList $ toSet $ do x <- s g x -- [1,2,3,101,102,103] print $ S.toList $ toSet $ do x <- s y <- g x return' y -- [1,2,3,101,102,103] print $ S.toList $ toSet $ do x <- s y <- g x g y -- [1,2,3,101,102,103,201,202,203] print $ S.toList $ toSet $ do x <- s y <- return (const x) -- no Ord! return' (y ()) -- [1,2,3] \end{code}

4 6

Re: [Haskell-cafe] State monad strictness - how?
by Yitzchak Gale 12 Jan '07

12 Jan '07

> ...how would one know that State is lazy and StateT is strict? > I don't see that in the Haddock documentation. You're right, it is not in the docs. I don't think anyone would have planned it that way. StateT is strict only because there happens to be a line in a do-expression that looks like: (a, s') <- runStateT m s The tuple pattern-match causes the strictness. That appears accidental, so it seems to be just an honest bug. Regards, Yitz

4 3

readFile problem
by Stefan Aeschbacher 12 Jan '07

12 Jan '07

Hi I am writing a network server in haskell. Lately I seem to have introduced a new bug. On Linux, when a client closes the connection to the server, the server dumps core. On Windows, the error message there is way different from the core dump on Linux. It says: application.exe: config.xml: openFile: does not exist (No such file or directory) I use readFile to read the config file. I tried to print out the config file after it is read to make sure that it is completely read. I only load this config file exactly once during program initialization. The config is used long before the crash. I printed the current working dir in the exception handler and there is something interesting. Instead of the path to the application, it is "\C:\\WINDOWS\\system32". There are many things i do not understand. Why the different behaviour on Linux and Windows? Shouldn't an exception be thrown on Linux instead of a core dump? I don't use any unsafePerformIO or foreign calls. Why the changed path? I never change working directory in my code. Why is a function (-> reading the config file) re-evaluated at a later point in time? How can I debug such a problem? My environement is ghc 6.6 on Ubuntu or Windows XP. thanks for any ideas Stefan

3 5

some way to reverse engineer lambda expressions out of the debugger?
by tphyahoo 12 Jan '07

12 Jan '07

I am a newbie learning haskell. (First forum post.) I am wondering if there is a trick to get debugging information about functions out of the environment (which for me, for now, is ghci). In this example, *UnixTools> :t map (*) [1,2] map (*) [1,2] :: (Num a) => [a -> a] This is very nice, but I would *really* like to see something like *UnixTools> explodeLambda( map (*) [1,2] ) [(\x -> 1*x),(\x -> 2*x)] Yes, maybe I'm dreaming, but I would like haskell to reverse engineer / pretty print lambda expressions for me. (Note that: *UnixTools> map ($ 5 ) [(\x -> 1*x),(\x -> 2*x)] [5,10] *UnixTools> map ($ 5) ( map (*) [1..2] ) [5,10] So these expressions really are the same, only it could be argued that the first expression is in some sense easier to read if you are debugging something complex. ) I would like to have something like "Data::Dumper" from perl, but of course, on steroids. Is something like this possible, or be worked on? Or probably never going to happen? Cheers, thomas. -- View this message in context: http://www.nabble.com/some-way-to-reverse-engineer-lambda-expressions-out-o… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 6

restricted existential datatypes
by oleg＠pobox.com 12 Jan '07

12 Jan '07

Misha Aizatulin wrote > I am using existential boxes like > > data Box cxt = forall a . Sat (cxt a) => Box a > here Sat is taken from [1]: > > class Sat a where dict :: a > The result is a box type which can have variable context imposed on > its contents. What I noticed is that sometimes I want to write functions > that operate on the Box and make use of some part of the context without > knowing the context completely. Such a function would look something > like this: > > f :: (Contains cxt ShowCxt) => Box cxt -> String > > f (Box a) = show a It seems what you'd like is an opaque datum that responds to (generally open) set of messages giving a reply dependent on a message. Sounds like an object, doesn't it? Why does it have to be an existential? True, existentials (that is, type abstraction) is one way to implement objects. There are other ways. Let's consider a very simple example: > data Box = forall a . Show a => Box a > f (Box a) = show a Now, the *only* meaningful thing we can do with the value `a' after unboxing is to pass it to the function `show'. Right? One may wonder why not to perform this application to show right upfront: > data Box1 = Box1 String > box a = Box1 (show a) This is _precisely_ equivalent to the above. Thanks to lazy evaluation, the application `show a' won't be evaluated unless we really need its value. The obvious benefit of Box1 is the simplicity of it: no existentials. The value 'Box1' is an object that responds to only one message, `show'. We'd like to have several messages, and we'd like to have the set of messages open. There are two choices: HList or the typeclasses. Both do the same thing, only the heterogeneous set of dictionaries is explicit in the former approach and implicit in the latter. Given below is the example. The box data constructor can be hidden in a module; its details are not important anyway. What is important is the membership in the Boxable class. The code below works with GHC 6.4.1 (no advanced versions required) and even in Hugs. {-# OPTIONS -fglasgow-exts #-} module RestrictedEx where -- Box labeled l responding to a message msg gives the result x class Boxable l msg x | l msg -> x where box_value :: l -> msg -> x -- A few message labels data SHow = SHow data CastToInt = CastToInt data Print = Print -- Create one box data MyBox1 = MyBox1 String -- Define its response to messages instance Boxable MyBox1 SHow String where box_value (MyBox1 s) _ = s instance Boxable MyBox1 Print (IO ()) where box_value (MyBox1 s) _ = putStrLn s -- A function that takes any box that can be shown f1 :: Boxable b SHow String => b -> String f1 b = box_value b SHow

1 0

UDP client/server
by John Ky 12 Jan '07

12 Jan '07

Hello, Does anyone know where I can find a simple UDP client/server written in Haskell? Something along the lines of an echo server would do. Thanks -John

4 6

MapTuple is possible and easy
by oleg＠pobox.com 11 Jan '07

11 Jan '07

Marco Tu'lio Gontijo e Silva wrote: > is there a way to defined something as a map to use in tuples? Yes, it is: and it is quite easy and straightforward. Udo Stenzel > since c would be a variable that ranges over type classes, and that > doesn't exist. Of course it does: please see below (as well as several earlier posts on the Haskell list showing that Haskell classes *are* first-class). Here's the definition of mapTuple > mapTuple l (x,y) = (apply l x, apply l y) and here its inferred type: > *MapTuple> :t mapTuple > mapTuple :: (Apply l b y1, Apply l a y) => l -> (a, b) -> (y, y1) Our mapTuple applies to (in general) heterogeneous tuples and gives (in general) a heterogeneous tuple. Here's the complete code and the tests. {-# OPTIONS -fglasgow-exts #-} module MapTuple where class Apply l x y | l x -> y where apply:: l -> x -> y data SHow = SHow instance Apply SHow String String where apply _ = show instance Apply SHow Int String where apply _ = show instance Apply SHow Bool String where apply _ = show mapTuple l (x,y) = (apply l x, apply l y) -- Here, the result is a homogeneous tuple test1 = mapTuple SHow ("a",(1::Int)) test2 = mapTuple SHow ((1::Int),"b") test3 = mapTuple SHow (True,"b") -- ANother operation: SUcc data SUcc = SUcc instance Apply SUcc String String where apply _ x = x ++ x instance Apply SUcc Int Int where apply _ = succ instance Apply SUcc Bool Bool where apply _ = not -- Here, the result is a heterogeneous tuple (as is the argument) testH1 = mapTuple SUcc ("a",(1::Int)) testH2 = mapTuple SUcc ((1::Int),"b") testH3 = mapTuple SUcc (True,"b")

1 0

an advanced foldification problem
by Seth Gordon 11 Jan '07

11 Jan '07

I have a data type "Group", representing a group of geographic information that is all referring to the same location, and a function "mergeGroups" that tries to merge two groups: mergeGroups :: Group -> Group -> Maybe Group Then I have a function "mergeGroupToList" that tries to merge its first argument with every element of the second argument: mergeGroupToList :: Group -> [Group] -> [Group] mergeGroupToList g [] = [g] mergeGroupToList g1 (g2:gs) = case (mergeGroups g1 g2) of Nothing -> g2 : (mergeGroupToList g1 gs) Just g3 -> mergeGroupToList g3 gs How can I rewrite mergeGroupToList in terms of foldr?

3 2

Re: [Haskell-cafe] State monad strictness - how?
by Yitzchak Gale 11 Jan '07

11 Jan '07

Dean Herington wrote: > I can't seem to figure out how to achieve strictness > in the context of the State monad. Unfortunately, the current situation is that State is only available as a lazy monad, and StateT is only available as a strict monad. It seems to me that this should clearly be considered a serious bug in the library. It has been reported on numerous occasions over the years, but it has still not been fixed. At the very least, the two should be consistent. I would much prefer for them both to be lazy. I have written a lot of code that depends on that; it is the natural assumption in Haskell that everything is lazy by default, except seq, IO, and their friends. The obvious solution would be to have available both a lazy and a strict version of each monad: State, State', StateT, and State'T (or some such), with functions to convert between them. It is trivial to implement that in the current library. If someone can come up with a more elegant solution right away, that would be great. (Iavor - do you have a solution?) Otherwise, I think we have waited long enough. Let's implement the simple fix. This bug is a major inconvenience to users of this library. > (try 1000000) overflows the stack. In the current situation, you can use > where final = runIdentity $ execStateT prog (0::Int) ... > tick :: (Num a, MonadState a m) => m a ... Regards, Yitz

10 18

Using PAPI to measure performance with CPU events
by Alexey Rodriguez Yakushev 11 Jan '07

11 Jan '07

Dear all, I have added a page to the GHC commentary explaining how to use the PAPI library together with GHC to gather performance information from your CPU (cache misses, branch misprediction). At present only cache miss information is supported in a platform independent way (though not tested). Also, this implementation separates the performance information for the garbage collector and the mutator so it is quite useful if you are implementing an optimisation. The page also has some patches to use PAPI on the nofib suite. These patches are eventually going to make it into the HEAD, but I thought someone might find them useful meanwhile. Cheers, Alexey

1 1