- Haskell-Cafe - Haskell.org

style question: Writer monad or unsafeIOToST?
by Gregory Wright 25 Aug '06

25 Aug '06

Hi, Thanks to the responses earlier from the list, the core of my simulator now happy processes tens of millions of state updates without running out of stack. The goal of the simulator is to produce a log of tag states, which can be analyzed to find statistics of how often the sensor tags in a particular state. (In the toy model below there is no external signal, so the log isn't very interesting yet.) For the moment, I am using the "big stick" approach of unsafeIOToST to write log messages. Since the only outputs of the program are the log messages, and invocations of "step" are ordered by the ST monad, it seems that unsafeIOToST is safe in this case, in the sense that the outputs will all be ordered the same as the actual state updates. I've tested the program test1.hs below and it quite fast (runs in just under 10 s, or about 10^6 state updates per second). I've considered using a WriterT monad to wrap the ST monad to produce a log. The problem with this seems to be ensuring that the log output is generated lazily so it can be incrementally output. A somewhat broken sketch is the program test2.hs below. I used a function from [String] -> [String] as the monoid to avoid the O(n^2) inefficiency of appending to a list, but my implementation of this may well be faulty. To my eye, the Writer monad should be a better way, since it encapsulates the logging process, separating it from other I/O that the program may do. On the other hand, I don't see an easy way to ensure that the log output is generated lazily so that it can be output incrementally. I think that the main issue is that until_ is building up a list of log strings, but that these aren't passed to the putStrLn until after the completion of the whole runTag function. ATM, running test2 gives a stack overflow. Could someone point out how the Writer monad could be adapted to this, or tell me that, "Real programmers just use unsafe* and get on with it" ? Best, greg ------------------------------------------------------------------------ ------------------------------ test1.hs, the big stick (unsafeIOToST): -- -- test1.hs, state updating with logging via unsafeIOToST. -- module Main where import Control.Monad.ST import Data.STRef import Maybe data TagState = Syncing | Listening | Sleeping deriving (Eq, Show) -- A structure with internal state: -- data Tag s = Tag { tagID :: ! Int, state :: ! (STRef s TagState), count :: ! (STRef s Integer) } data FrozenTag = FrozenTag { ft_tagID :: Int, ft_state :: TagState, ft_count :: Integer } deriving Show -- Repeat a computation until it returns Nothing: -- until_ :: Monad m => m (Maybe a) -> m () until_ action = do result <- action if isNothing result then return () else until_ action -- Here is a toy stateful computation: -- runTag :: ST s (FrozenTag) runTag = do tag <- initialize until_ (step tag) freezeTag tag initialize :: ST s (Tag s) initialize = do init_count <- newSTRef 1000000 init_state <- newSTRef Syncing return (Tag { tagID = 1, state = init_state, count = init_count }) step :: Tag s -> ST s (Maybe Integer) step t = do c <- readSTRef (count t) s <- readSTRef (state t) writeSTRef (count t) $! (c - 1) writeSTRef (state t) $! (nextState s) unsafeIOToST $! putStrLn ("next state is " ++ show s) if (c <= 0) then return Nothing else return (Just c) nextState :: TagState -> TagState nextState s = case s of Syncing -> Listening Listening -> Sleeping Sleeping -> Syncing freezeTag :: Tag s -> ST s (FrozenTag) freezeTag t = do frozen_count <- readSTRef (count t) frozen_state <- readSTRef (state t) return (FrozenTag { ft_tagID = tagID t, ft_count = frozen_count, ft_state = frozen_state }) main :: IO () main = do print $ runST (runTag) ------------------------------------------------------------------------ ----------------------------------------- test2.hs: stacked WriterT and ST monads: -- -- test2.hs, state updating with logging via the WriterT monad. -- module Main where import Control.Monad.ST import Control.Monad.Writer import Data.STRef import Maybe data TagState = Syncing | Listening | Sleeping deriving (Eq, Show) -- A type for combined logging and state transformation: -- type LogMonoid = [String] -> [String] type LogST s a = WriterT LogMonoid (ST s) a -- A structure with internal state: -- data Tag s = Tag { tagID :: ! Int, state :: ! (STRef s TagState), count :: ! (STRef s Integer) } data FrozenTag = FrozenTag { ft_tagID :: Int, ft_state :: TagState, ft_count :: Integer } deriving Show -- Repeat a computation until it returns Nothing: -- until_ :: Monad m => m (Maybe a) -> m () until_ action = do result <- action if isNothing result then return () else until_ action -- Here is a toy stateful computation: -- runTag :: LogST s (FrozenTag) runTag = do tag <- initialize until_ (step tag) freezeTag tag initialize :: LogST s (Tag s) initialize = do init_count <- lift $ newSTRef 1000000 init_state <- lift $ newSTRef Syncing return (Tag { tagID = 1, state = init_state, count = init_count }) step :: Tag s -> LogST s (Maybe Integer) step t = do c <- lift $ readSTRef (count t) s <- lift $ readSTRef (state t) lift $ writeSTRef (count t) $! (c - 1) lift $ writeSTRef (state t) $! (nextState s) tell (("next state is " ++ show s) : ) if (c <= 0) then return Nothing else return (Just c) nextState :: TagState -> TagState nextState s = case s of Syncing -> Listening Listening -> Sleeping Sleeping -> Syncing freezeTag :: Tag s -> LogST s (FrozenTag) freezeTag t = do frozen_count <- lift $ readSTRef (count t) frozen_state <- lift $ readSTRef (state t) return (FrozenTag { ft_tagID = tagID t, ft_count = frozen_count, ft_state = frozen_state }) main :: IO () main = do let (t, l) = runST (runWriterT runTag) putStrLn (show t) putStrLn (unlines (l []))

3 10

monads once again: a newbie perspective
by Andrea Rossato 25 Aug '06

25 Aug '06

Hello! I' m new to Haskell and try to find my way through types and monads. I tried the yet Another Haskell Tutorial, very useful for types, but almost unreadable for monads (that's my perspective!). Then I discovered that wonderful paper by Wadler (Monads for functional programming). So I started "translating it" for someone who can be scared of something with an abstract and footnotes coming from a professor. I started writing it in order to clarify to myself this difficult topic. I think I'm now grasping the concept of monads. I thought that someone else could find my writings useful. It could become a page on the wiki. But before posting there I would like to have your opinion. Perhaps this is just something unreadable. Let me know. Andrea

3 3

stack overflow when using ST monad
by Gregory Wright 25 Aug '06

25 Aug '06

Hi, I have a program, abstracted from a larger application that I am writing for a customer, that persistently overflows its stack. The program is a simulation of the communication protocol of a sensor tag. The code is below. The program mimics a hardware state machine. In the example below, the internal state is just a counter and a another register that holds what is called the tag's "state": Syncing, Listening or Sleeping. The simulation just advances the tags internal state until the counter reaches zero. (In the real application, there are external inputs that can change the state, but that's not needed to see the problem.) The simulation crashes, running out of stack space after only about 400000 cycles on my machine (OS X 10.4.7 ppc). Both hugs and ghci show it: hugs -98 Test2.hs Hugs mode: Restart with command line option +98 for Haskell 98 mode Type :? for help Main> main ERROR - Garbage collection fails to reclaim sufficient space Main> and ghci: Prelude> :load "/Users/gwright/src/haskell/simulator/test2.hs" Compiling Main ( /Users/gwright/src/haskell/simulator/ test2.hs, interpreted ) Ok, modules loaded: Main. *Main> main FrozenTag {ft_tagID = 1, ft_state = *** Exception: stack overflow *Main> Searches through old mailing lists warn me that it can be hard to tell if evaluation is truly tail recursive, and I saw a discussion of this in the context of "monadic loops", but I never saw a solution. Perhaps in my sleep deprived condition I am missing the obvious, but any help would be appreciated. Best, Greg -- -- Test the state transformer calculation. -- -- 21 August 2006 -- module Main where import Control.Monad.ST import Control.Monad.Writer import Data.STRef import Maybe data TagState = Syncing | Listening | Sleeping deriving (Eq, Show) -- A structure with internal state: -- data Tag s = Tag { tagID :: Int, state :: STRef s TagState, count :: STRef s Integer } data FrozenTag = FrozenTag { ft_tagID :: Int, ft_state :: TagState, ft_count :: Integer } deriving Show -- Repeat a computation until it returns Nothing: -- until_ :: Monad m => m (Maybe a) -> m () until_ action = do result <- action if isNothing result then return () else until_ action -- Here is a toy stateful computation: -- runTag :: ST s (FrozenTag) runTag = do tag <- initialize until_ (step tag) freezeTag tag initialize :: ST s (Tag s) initialize = do init_count <- newSTRef 1000000 init_state <- newSTRef Syncing return (Tag { tagID = 1, state = init_state, count = init_count }) step :: Tag s -> ST s (Maybe Integer) step t = do c <- readSTRef (count t) s <- readSTRef (state t) writeSTRef (count t) (c - 1) writeSTRef (state t) (nextState s) if (c <= 0) then return Nothing else return (Just c) nextState :: TagState -> TagState nextState s = case s of Syncing -> Listening Listening -> Sleeping Sleeping -> Syncing freezeTag :: Tag s -> ST s (FrozenTag) freezeTag t = do frozen_count <- readSTRef (count t) frozen_state <- readSTRef (state t) return (FrozenTag { ft_tagID = tagID t, ft_count = frozen_count, ft_state = frozen_state }) main :: IO () main = do putStrLn (show (runST runTag))

5 9

Fran - Functional Reactive Animation
by HIGGINS Neil (ENERGEX) 25 Aug '06

25 Aug '06

> Fran is a Haskell library (or "embedded language") for interactive > animations with 2D and 3D graphics and sound. See > <http://www.conal.net/fran/ <http://www.conal.net/fran/> > and > <http://research.microsoft.com/research/downloads/download.aspx?FUID=c9eff > 407-ce59-4a2a-90cb-de099a9bacbd > <http://research.microsoft.com/research/downloads/download.aspx?FUID=c9eff > 407-ce59-4a2a-90cb-de099a9bacbd> > > > I would like to use Fran as a rapid prototyping environment for > animations, but it appears to be broken under WinHugs. > > I'm looking for someone with much better Haskell prowess than myself who > might be able resurrect Fran under WinHugs. Unfortunately I can only offer > my gratitude in return. > > It's a long shot, I know. > Kind regards, > Neil Higgins > Snr Strategic Planning Engineer > ENERGEX > Em: neilhiggins(a)energex.com.au > Ph: 3407 4800 > Fx: 3407 4832 > ************************************************************************* This email message (including any file attachments transmitted with it) is for the sole use of the intended recipient(s) and may contain confidential and legally privileged information. Any unauthorised review, use, alteration, disclosure or distribution of this email (including any attachments) by an unintended recipient is prohibited. If you have received this email in error, please notify the sender by return email and destroy all copies of the original message. Any confidential or legal professional privilege is not waived or lost by any mistaken delivery of the email. ENERGEX accepts no responsibility for the content of any email which is sent by an employee which is of a personal nature. Sender Details: ENERGEX GPO Box 1461 Brisbane QLD Australia 4001 +61 7 3407 4000 http://www.energex.com.au ENERGEX policy is to not send unsolicited electronic messages. Suspected breaches of this policy can be reported by replying to this message including the original message and the word "UNSUBSCRIBE" in the subject. *************************************************************************

3 2

wiki page Arrays updated
by Bulat Ziganshin 24 Aug '06

24 Aug '06

Hello Haskell-Cafe, i've added a lot of low-level information to the Arrays wiki page. new material starts from note about GHC 6.6 in http://haskell.org/haskellwiki/Modern_array_libraries#StorableArray_.28modu… there are several details, however, which makes it imperfect. first, as usual, is my awkward English. please correct my language misuse. in particular, i don't know how to better name the page itself, meaning "modern library which implements many array types" second is that it will be great to add examples demonstrating each discussed concept: casting, freezing, unsafe indexing, [::]. we also still don't have examples for unboxed and diff arrays third is that i'm not 100% sure that information about GHC internals i provided is correct. can someone with a good knowledge of RTS internals check it, including http://haskell.org/haskellwiki/Modern_array_libraries#Welcome_to_machine:_A… and next section plus abovementioned link with information about StorableArray in GHC 6.6? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

implementing a csv reader
by Tamas K Papp 24 Aug '06

24 Aug '06

Hi, Now that I have read the tutorials, I think that the best way to learn Haskell would be to use the language and write something simple yet useful. I noticed that Haskell lacks a module for reading/writing csv (comma separated value) files, so I thought I could implement that. Questions: 1. Please tell me if you know of a csv module, because then I would do something else. 2. I am looking for a parser, but I don't know Haskell parsers. Is Parsec a good choice? Thanks, Tamas

12 13

question on traversing syntax tree
by Xiong Yingfei 24 Aug '06

24 Aug '06

I am writing a compiler using Haskell. After the compiler parses program, the program is stored into an syntax tree stucture defined blew: ...... data Exp = Plus Exp Term | Minus Exp Term | Term Term deriving Show data Term = Times Term Factor | Div Term Factor | Factor Factor deriving Show ...... This is just part of the definition. The full tree contains much more definition than this. Now I want to adjust the syntax-tree. However, I don't need to adjust all the data types, but a small subset of the syntax tree. e.g. I might adjust the "Times" data like the following, but not modify the rest of the syntax tree: transformTerm (Times t f) = Times t (FactorInt 100) However, in order to apply the modification like this, I have to write a series of function to traverse the tree until I get to the Term data type. e.g. I have to define: transformExp (Plus e t) = Plus (transformExp e) (transformTerm t) transformExp (Minus e t) = Minus (transformExp e)(transformTerm t) transformTerm (Term t) = ... This is tedious and error-prone. I want to know if there some means in Haskell to write a single "generic" function to traverse the syntax tree and only stop on the "Term" data type. Can anyone tell me something about it? Thanks a lot. -- Xiong, Yingfei (熊英飞) Ph.D. Student Institute of Software School of Electronics Engineering and Computer Science Peking University Beijing, 100871, PRC. Web: http://xiong.yingfei.googlepages.com

2 1

Cabal question, adding data files
by Neil Mitchell 24 Aug '06

24 Aug '06

Hi, I have a cabal executable, which requires additional data files. How do I do this in Cabal? I have seen extra-source-files, but they are not added at install time to the destination directory, which doesn't help me. I noticed that Alex does this, but with a lot of Cabal calling in Setup.hs with hooks etc, which is not really ideal. Is there any easy way to do the "install these files along with the program, please" ? If anyone needs any concrete examples, take for example HsColour, which needs the files .hscolour and hscolour.css, but currently install doesn't put either of them anywhere useful. Thanks Neil

3 3

Proposal to allow {} instead of () in contexts
by Brian Hulley 24 Aug '06

24 Aug '06

Hi - Disregarding my last proposal which involved the use of {} in types, I am wondering if anyone would agree with me that it would be a good idea to use {} instead of () when writing out the context ie: foo :: (Num a, Bar a) => a -> a would become: foo :: {Num a, Bar a} => a -> a and the same for every other situation in the language where a context appears. My reasons are twofold: 1) The context is supposed to be understood (afaiu) as a *set* of constraints not a *tuple* of constraints (ie what relevance does the ordering implied by the tuple notation have here?), so the using of set braces seems mathematically more appropriate 2) It would allow an editor to give the correct fontification for an incomplete type expression. At the moment, if you'd just typed: foo :: (Bar the editor would have no way of knowing if "Bar" is a classcon or a tycon, whereas with: foo :: {Bar the opening brace immediately informs the editor that the following text should be parsed as a context and so it could fontify Bar appropriately. For backwards compatibility the use of () could still be supported - braces don't occur in H98 in the positions I'm proposing to allow them so nothing would be broken. Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com

2 2

One thought: Num to 0 as ? to list?
by Marc Weber 24 Aug '06

24 Aug '06

Is there somethinig corresponding to Num concering lists? I mean there is + - /.. defined. + - are not type specific (Int, Double) neither is : [1,2] notation to Elements.. But what about different implementatins of lists? (linked lists? hash lists? array with index? In other words: why not overload (:) ? Then it would be possible to use "blah" for fast packed strings, too Then you could also implement implementations for C arrays and access them. (Sure you can do it anyway but not using syntactic sugar) One part of the answer is patterns? f 'a' = .. f _ = .. Marc

12 28