- Haskell-Cafe - Haskell.org

A free monad theorem?
by Benjamin Franksen 04 Sep '06

04 Sep '06

I'd like to know if the following reasoning can be made more precise: As we all know, the monadic bind operation has type: bind :: Monad m => m a -> (a -> m b) -> m b My intuition says that in order to apply the second argument to some non-trivial (i.e. non-bottom) value of type a, the bind operator needs to be able to somehow 'extract' a value (of type a) from the first argument (of type m a). I would like to argue that this is because bind is polymorphic in a, which makes it impossible to construct values of type a 'out of thin air' (besides bottom). Thus, however bind is defined, the only place where it can obtain a 'real' value of type a is from its first argument. Although one might think that this implies the existence of some function extract :: Monad m => m a -> a it is obvious that this is too limiting, as the IO monad plainly shows. Even monads that can be implemented in Haskell itself (the vast majority, it seems) usually need some additional (monad-specific) argument to their 'extract' (or 'run') function. However, even a value of type IO a /does/ produce a value of type a, only the 'value producing computation' is not a (pure) function. But how can all this be made more precise with less handwaiving? The background for my question is an argument I had some time ago with someone about what the 'real nature' of monads is. He argued that monads are mainly about 'chaining' (somehow wrapped up) values in an associative way, refering to the monad laws. I argued that monadic values get 'chained' in a very specific way and that in order to get an intuition about what this monadic chaining really means on the most general level, the standard model of 'computation that returns a value of type a' is the appropriate one. I tried to use the above (handwaving) argument to convince him (and myself) that this model is indeed 'the right one'. Furthermore, if it really is, then one might conjecture that for /every/ monad there must be some natural interpretation as the representation of some kind of computation (effectful or not). So my second question is: Are there known 'counter-examples' where this intuition breaks down, i.e. monads for which a computational interpretation is unknown or at least obscure enough not to qalify as 'natural'? Cheers, Ben

12 27

Re: [Haskell-cafe] practice problems?
by Paul Johnson 03 Sep '06

03 Sep '06

"Brian Hulley" <brianh(a)metamilk.com> wrote: What about a library for interval arithmetic [1]? I'd imagine it could start something like: data Interval a = Interval !a !a deriving (Eq, Show) instance Num a => Num (Interval a) where Interval llow lhigh + Interval rlow rhigh = Interval (min llow rlow) (max lhigh rhigh) The Interval type would probably need to explicitly represent several kinds of intervals eg (-infinity, x] etc and there are some tricky issues about what to do with the operations whose result sometimes needs to be represented by more than one interval to be useful such as division by an interval containing zero eg you might want to use a list of intervals to deal with these cases: instance Num a => [Interval a] where ... ie [Interval 5 5] / [Interval -1 1] = [FromNegInfinityTo -5, ToPosInfinityFrom 5] Take a look at my Ranged Sets library at http://sourceforge.net/projects/ranged-sets Paul.

2 1

beginner's problam with a monad
by Julien Oster 03 Sep '06

03 Sep '06

Hello, after succeeding in implementing my first monad (Counter, it increments a counter every time a computation is performed) I though I'd try another one and went on to implement "Tracker". "Tracker" is a monad where a list consisting of the result of every computation is kept alongside the final value, kind of a computation history. It really just serves me as an exercise to implement monads. However, the following source code fails: {-------------------------------------------------} data Tracker a b = Tracker [a] b deriving Show instance Monad (Tracker a) where m >>= f = let Tracker l x = m in let Tracker l' x' = f x in Tracker (x':l) x' return x = Tracker [] x bar = do x <- Tracker [] 12 y <- return (x*2) z <- return (y*3) return (z+3) {-------------------------------------------------} Of course, style recommendations and the like are always appreciated. (by the way, I don't really understand why I have to type instance Monad (Tracker a) instead of instance Monad Tracker which may very well be the problem. If it's not, can someone tell me anyway?) Trying to load this piece of code leads to the following error message: Hugs.Base> :load Test.hs ERROR "Test.hs":30 - Inferred type is not general enough *** Expression : (>>=) *** Expected type : Monad (Tracker a) => Tracker a b -> (b -> Tracker a c) -> Tracker a c *** Inferred type : Monad (Tracker a) => Tracker a b -> (b -> Tracker a a) -> Tracker a a Why does the interpreter infer Tracker a a instead of the more general Tracker a c? Thanks, Julien

4 5

[JOKE] Foozles: anatomy of a programming language fad
by Stephane Bortzmeyer 02 Sep '06

02 Sep '06

http://hope.cs.rice.edu/twiki/pub/WG211/M3Schedule/foozles.pdf I hope many Haskellers will have laugh here :-)

1 0

Re: [Haskell-cafe] state and exception or types again...
by Andrea Rossato 02 Sep '06

02 Sep '06

Il Wed, Aug 30, 2006 at 11:24:45AM +0100, Brian Hulley ebbe a scrivere: > Thanks, glad to be of help. I met Haskell a couple of months ago, when I switched my window manager to Ion. Tuomo Valkonen, its developer, uses darcs. Moreover he develops a small PIM, riot, written in Haskell. I wanted to play around with it but the source code was literally unreadable, for me. I could not understand a single line. I do some php. Lately I discovered Javascript and Lua, and I fell in love with their object-oriented capabilities. I'm not a real coder (though I develop a wiki in php), but I like getting to know new programming practices. I've been intrigue with functional programming for quite sometime but I just knew a bit of Scheme, because it's used as a scripting language in LilyPond (a package for writing music sheets). So I decided to spend my August holidays to study Haskell. I started reading some tutorial but could not understand what was going on. I then thought to take the long way: I watched the Abelson and Sussman's lectures and used ghci to (sort of) follow what they were doing. Coming from dynamic typed languages (I know very little C) the type system was horrible. Monads seemed mysterious objects. I've read in the "Yet Another..." that the Haskell community is very supportive. With your help I have now a different perspective. Playing with Haskell is like completing a puzzle, whose pieces' shapes are made up with rules that, at first, you seem not be able to grasp. You keep pushing the last piece, and it just doesn't fit in. Then you realize that shapes are actually types. And when you start understanding the rules of type construction and type matching, now you can recognize the shapes of the pieces you are playing with. And start making rational guesses on where they should go. Now, when I see "Compiling ... Ok, modules loaded: " I feel like I ended up solving the puzzle. It's an amazing pleasure... Haskell and functional programming. Without you I couldn't do it. Thank you so much! The tutorial will have this outline: first we build a monad adding output, exception, and state. Then we use monad transformer to take out state and output and add debug, doing lifting, put(ing) and get(ing) by hand, to understand the central role of type matching/construction. We end up with the following code, that should clearly show all the previous (hand made) steps should lead. No lambda calculus inhere! Once again, thanks! Andrea -----The Final Evaluator---- module MyStateT where import Control.Monad.State hiding (State) data Term = Con Int | Add Term Term deriving (Show) type IOStack = [Output] type Output = String type Debug = [String] data EvalST = State {getIOS :: IOStack, getDebug :: Debug, getCount:: Int} deriving(Show) type Exception = String data MT a = Fail Exception | Done {unpackDone :: a } deriving (Show) type Eval s a = StateT s MT a instance Monad MT where return a = Done a m >>= f = case m of Fail e -> Fail e Done a -> f a instance Functor MT where fmap _ (Fail a) = Fail a fmap f (Done a) = Done (f a) emptyState = State [] [] 0 stopExecT exc = lift $ Fail exc catchT e = do st <- get let s = getCount st let es = getDebug st let o = getIOS st let exc = "Debug msg at Iteration " ++ show s ++ ": " ++ e put $ State o (exc:es) s printT :: Output -> Eval EvalST () printT o = do st <- get let s = getCount st let e = getDebug st let os = getIOS st let out = show s ++ " - " ++ o put $ State (out:os) e s incTcounter :: Eval EvalST () incTcounter = do st <- get let s = getCount st let e = getDebug st let o = getIOS st put $ State o e (s+1) evalT :: Term -> Eval EvalST Int evalT (Con a) = do incTcounter printT (formatLine (Con a) a) return a evalT (Add t u) = do a <- evalT t b <- evalT u incTcounter let out = formatLine (Add t u) (a + b) printT out case (a+b) of 42 -> do catchT "The Ultimate Answer Has Been Computed!! Now I'm tired!" return (a+b) 11 -> stopExecT "11.... I do not like this number!" otherwise -> return (a + b) formatLine :: Term -> Int -> Output formatLine t a = "eval (" ++ show t ++ ") <= " ++ show a printAll :: [String] -> IO () printAll [] = return () printAll (a:xs) = do print a printAll xs eval :: Term -> IO () eval exp = case execStateT (evalT exp) emptyState of Fail e -> print e Done (State a b c ) -> do printAll $ reverse a print $ show $ unpackDone $ evalStateT (evalT exp) emptyState case b of [] -> print $ "Iterations: " ++ show c _ -> do printAll $ reverse b print $ "Iterations: " ++ show c {- Some runs: *MyStateT> eval (Add (Add (Add (Add (Con 40) (Con 2)) (Add (Con 12) (Con 3))) (Con 3)) (Con 10)) "1 - eval (Con 40) <= 40" "2 - eval (Con 2) <= 2" "3 - eval (Add (Con 40) (Con 2)) <= 42" "4 - eval (Con 12) <= 12" "5 - eval (Con 3) <= 3" "6 - eval (Add (Con 12) (Con 3)) <= 15" "7 - eval (Add (Add (Con 40) (Con 2)) (Add (Con 12) (Con 3))) <= 57" "8 - eval (Con 3) <= 3" "9 - eval (Add (Add (Add (Con 40) (Con 2)) (Add (Con 12) (Con 3))) (Con 3)) <= 60" "10 - eval (Con 10) <= 10" "11 - eval (Add (Add (Add (Add (Con 40) (Con 2)) (Add (Con 12) (Con 3))) (Con 3)) (Con 10)) <= 70" "70" "Debug msg at Iteration 3: The Ultimate Answer Has Been Computed!! Now I'm tired!" "Iterations: 11" *MyStateT> *MyStateT> eval (Add (Add (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) (Add (Con 5) (Con 2))) (Con 2)) "1 - eval (Con 10) <= 10" "2 - eval (Con 2) <= 2" "3 - eval (Add (Con 10) (Con 2)) <= 12" "4 - eval (Con 12) <= 12" "5 - eval (Con 3) <= 3" "6 - eval (Add (Con 12) (Con 3)) <= 15" "7 - eval (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) <= 27" "8 - eval (Con 5) <= 5" "9 - eval (Con 2) <= 2" "10 - eval (Add (Con 5) (Con 2)) <= 7" "11 - eval (Add (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) (Add (Con 5) (Con 2))) <= 34" "12 - eval (Con 2) <= 2" "13 - eval (Add (Add (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) (Add (Con 5) (Con 2))) (Con 2)) <= 36" "36" "Iterations: 13" *MyStateT> *MyStateT> eval (Add (Con 5) (Con 6)) "11.... I do not like this number!" *MyStateT> -}

2 3

Rewriting a Python application to Haskell
by basvandijk＠home.nl 02 Sep '06

02 Sep '06

Hello, The company I work for [1] develops highly sensitive trace gas detectors. We also develop software that is used to control these detectors from a PC or laptop. With this software a user can setup an experiment, execute it and analyse and visualise the data in real-time. While executing, the application gives commands to the detector and gets concentrations from the detector which it plots. See [5] for a screenshot. The application is written in Python and uses wxPython for its GUI. The software is highly threaded; The experiment executor, the analyzer, the communication system and the GUI all have their own threads. In order to synchronise these threads we make extensive use of locks [2]. This thread synchronisation mechanism worked fine in the beginning. However, as the application becomes more complex, it is increasingly difficult not to introduce bugs that are caused by forgetting to release or acquire locks. Also the use of locks makes the code hard to understand. Finally it's hard to compose functions that use locks. I've long been interested in Haskell and played around with it for some time. Recently I became aware of the Haskell STM implementation [3]. I think STM can solve my thread synchronisation problems. Because of this and because I would like to know how suitable Haskell is for developing real-world GUI applications, I would like to rewrite our application in Haskell (in my free time of course ;-) ). I think I need to use wxHaskell for the GUI because it's runs on a lot of platforms and we are currently using wxPython which should make the transition easier. 1) I would like to know if its difficult to use wxHaskell and STM side by side and if there are any issues I need to know about. 2) Also, we use pySerial [4] for serial communication with the detector. Is there something like that for Haskell or is it easy to make it yourself? 3) How portable is Haskell? We like to run our application on Mac, Windows and Linux. Greetings, Bas van Dijk [1] http://www.sensor-sense.nl [2] http://docs.python.org/lib/lock-objects.html [3] http://haskell.org/ghc/docs/latest/html/libraries/stm/Control-Concurrent-ST… [4] http://pyserial.sourceforge.net [5] http://members.home.nl/basvandijk/vc-screenshot.png

4 4

Re: [Haskell-cafe] getContents and lazy evaluation
by Donn Cave 02 Sep '06

02 Sep '06

Quoth Julien Oster <haskell(a)lists.julien-oster.de>: ... | But what happens when two processes use the same file and one process is | writing into it using lazy IO which didn't happen yet? The other process | wouldn't see its changes yet. That's actually a much more general problem, one that I imagine applies to hPutStr et al. too. Application level writes are ordinarily buffered in process space by the I/O library, so output from an ordinary C program may not appear on disk (or in kernel space disk I/O buffer) until just before the program exits. | As for two processes writing to the same file at the same time, very bad | things may happen anyway. Sure, lazy IO prevents doing communication | between running processes using plain files, but why would you do | something like that? Quite a few reasons, depending on how you define communication. You might even be tempted to use hGetContents in such cases. For example, one common way to share a file is to interlock around some resource, and when you acquire the lock, you read the file (get its contents) and release the lock. Donn Cave, donn(a)drizzle.com

1 0

Re: Exercise in point free-style
by John Hughes 02 Sep '06

02 Sep '06

> From: Julien Oster <haskell(a)lists.julien-oster.de> > Subject: [Haskell-cafe] Exercise in point free-style > > I was just doing Exercise 7.1 of Hal Daumé's very good "Yet Another > Haskell Tutorial". It consists of 5 short functions which are to be > converted into point-free style (if possible). > > It's insightful and after some thinking I've been able to come up with > solutions that make me understand things better. > > But I'm having problems with one of the functions: > > func3 f l = l ++ map f l > > Looks pretty clear and simple. However, I can't come up with a solution. > Is it even possible to remove one of the variables, f or l? If so, how? > > Thanks, > Julien Oh, YES!! Two ways to remove l: func3a f = uncurry ((.map f).(++)) . pair func3b f = uncurry (flip (++).map f) . pair And just to make sure they're right: propab new f l = func3 f l == new f l where types = f :: Int->Int quickCheck (propab func3a) quickCheck (propab func3b) If you don't mind swapping the arguments, then propc f l = func3 f l == func3c l f where types = f :: Int->Int func3c l = (l++) . (`map` l) With the arguments swapped, you can even remove both! propd f l = func3 f l == func3d l f where types = f :: Int -> Int func3d = uncurry ((.(flip map)) . (.) . (++)) . pair MUCH clearer! The trick is to observe that l is duplicated, so you need to use a combinator that duplicates something. The only one available here is pair, which you then have to combine with uncurry. It would be nicer to have (f &&& g) x = (f x,g x) available. (&&& is one of the arrow combinators). Then you could remove l by func3e f = uncurry (++) . (id &&& map f) which is sort of readable, and remove both by func3f = (uncurry (++).) . (id &&&) . map John

3 2

data structures question
by Tamas K Papp 01 Sep '06

01 Sep '06

Hi, Having read some tutorials, I would like to start using Haskell "for real", but I have some questions about data structures. The mathematical description of the problem is the following: assume there is a function V(a,b,theta), where a and b can have two values, High or Low, and theta is a number between zero and n (n is given). The range of V is the real numbers. Then there is an algorithm (called value iteration, but that's not important) that takes V and produces a function of the same type, called V'. The algorithm uses a mapping that is not elementwise, ie more than the corresponding values of V are needed to compute a particular V'(a,b,theta) -- things like V(other a,b,theta) and V(a,b,theta+1), where data State = Low | High other :: State -> State other High = Low other Low = High Question 1: V can be represented as a 3-dimensional array, where the first two indices are of type State, the third is Int (<= n). What data structure do you suggest in Haskell to store V? Is there a multidimensional array or something like this? Let's call this structure TypeV. Question 2: I would like to write valueit :: TypeV -> TypeV valueit V = mapondescartesproduct [Low,High] [Low,High] [0..n] mapV where -- mapV would calculate the new V' using V -- mapV :: State -> State -> Int -> Double to fill the new data structure. How to do this sensibly? Thanks, Tamas

6 12

HaXml question
by Tim Newsham 01 Sep '06

01 Sep '06

I thought this one would be easy but I'm starting to think its not. I am playing with HaXml and I want to transform an XML tree into another tree. The transforms are simple enough, but the kicker is that I want them to be "stateful." In this example, the state is a random number generator. So the transformation depends on the current node and the random number generator state. I want to transform every node in the tree. My feeble attempt at this is given in: http://www.thenewsh.com/~newsham/x/tweaker.hs What I see when I run it is that the value of "p" in the "tweak" function is identical each time. Indeed, it seems "g" itself is the same each time "tweak" is invoked (I wrote a variant of the program that used sequential integers instead of generators to verify this). So here's what I think is going on. You can probably skip this section because I am probably off base anyway... I guess "keep" is being applied to one node, and returning a list of 1 node, and this is zipped with my infinite list of generators and as a result I get the same generator each time. If this is the case I guess foldXml is not the right tool for this job. Perhaps I want a newly-written foldXml that works with LabelFilters rather than CFilters? Ok.. so what's really going on here. Can I do what I want to do? Whats the right tool to transform every node in the tree? Is there a more general approach to doing stateful transformations? Thanks in advance for letting me waste your time. P.S. any stylistic advice, or alternate approaches also welcome. The objective here is to learn... Tim Newsham http://www.thenewsh.com/~newsham/

2 1