- Haskell-Cafe - Haskell.org

state updates and efficiency
by Tim Newsham 06 Dec '06

06 Dec '06

I am writing some code with complex nested state. I have a question about performance with respect to the State monad and the Reader monad. This is somewhat long, so a quick summary of the question up front: Can the compiler optimize out state updates that dont change the state? The question inline with the code: > module Test where > import Control.Monad.State > import Control.Monad.Reader I have some nested state. This is a simplified example where we have one record inside another. In my real-world example there is more nesting and there are lists and maps involved as well. > data T1 = T1 { f1 :: Int, f2 :: T2 } deriving(Show) > data T2 = T2 { f3 :: Int, f4 :: Int } deriving(Show) I want to build generic modifiers and reuse them often. A good example is modifying a numeric value: > adjNum :: (Num a) => a -> State a () > adjNum n = modify (+ n) I'm going to be writing state code for my T1 structure which is my master structure. If I'm going to be able to reuse adjNum I am going to have to run a nested state action inside an enclosing state monad. I can build a lifter that does this as long as I know how to extract the nested state and set it back in the enclosing state: > withInnerM :: (o -> i) -> (i -> o -> o) -> State i a -> State o a > withInnerM gettor settor act = do > outer <- get > let inner = gettor outer > (ret, inner') = runState act inner > outer' = settor inner' outer > put outer' > return ret Now we can make lifters for each of the fields: > withF1M = withInnerM f1 (\f r -> r {f1=f}) > withF2M = withInnerM f2 (\f r -> r {f2=f}) > withF3M = withInnerM f3 (\f r -> r {f3=f}) > withF4M = withInnerM f4 (\f r -> r {f4=f}) which lets us write some state code for T1 using building blocks like adjNum. For example, the following code will add a value to f1, add another value to f2's f3 and finally return the value of f2's f4: > tweakT1 :: Int -> Int -> State T1 Int > tweakT1 v1 v3 = do > withF1M $ adjNum v1 > withF2M $ withF3M $ adjNum v3 > withF2M $ withF4M $ get My question here has to do with efficiency. In order to update f2's f3 a new T2 had to be constructed and used to construct a new T1. There's no way around this (I assume). But when doing a mere get of f4, there's no reason why we should have to build a new T2 and then a new T1 since nothign changed. But that's how the code is written. We could write a different lifter that does not perform a state put on the return path. If we did this with the state monad then someone could accidentally use that non-modify version of the lifter and lose an update. So instead I chose to use the Reader monad and let the type system enforce the difference between lifters that modify (M) and those that just read (R). This involved two kinds of lifters. The first lifter runs a Reader action inside of a State monad: > withRead :: Reader s a -> State s a > withRead act = do > s <- get > return $ runReader act s The second lifter runs a nested Reader action inside of an enclosing Reader monad. It is similar in spirit to withInnerM: > withInnerR :: (o -> i) -> Reader i a -> Reader o a > withInnerR gettor act = do > i <- asks gettor > return $ runReader act i again we can generate lifters for each field: > withF1R = withInnerR f1 > withF2R = withInnerR f2 > withF3R = withInnerR f3 > withF4R = withInnerR f4 And finally we can use a reader monad to eliminate the extra state updates from our previous tweakT1 implementation: > tweakT1' :: Int -> Int -> State T1 Int > tweakT1' v1 v3 = do > withF1M $ adjNum v1 > withF2M $ withF3M $ adjNum v3 > withRead $ withF2R $ withF4R $ ask > > main = do > let x = T1 1 (T2 3 4) > print $ runState (tweakT1 5 6) x > print $ runState (tweakT1' 5 6) x My question here is: is it worth it? If I run > v1 = T2 1 1 > v2 = v1 {f3 = 1} is the compiler smart enough to notice that the record update doesn't result in a change, and avoid constructing an entirely new T2? If so, then I think the original implementation TweakT1 would be about as efficient as the more complicated TweakT1'. Otherwise, I think the latter would be a lot more efficient when the state is large and complex. Tim Newsham http://www.thenewsh.com/~newsham/

2 2

what GUI library should i select?
by Bulat Ziganshin 06 Dec '06

06 Dec '06

Hello haskell-cafe, afaik, there are just two good enough libs - wxHaskell and GtkHs. can anyone point (or write) detailed comparison of their features? i plan to write large GUI program in Haskell and want to select best one. the requirements that i can imagine at this moment is the following: * my main target is Windows but ability to compile the same code both for Windows and Linux would be a plus * the program developed is a sort of advanced file manager, so i need treeview, table view and tabbed view controls * user likes beauty, so various bells-and-whistles are welcomed. in particular, it would be great to have skinnable interface * use of resource file for all texts to make internalization easier -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

15 39

(a -> [b]) -> [a -> b] ?
by Joachim Breitner 06 Dec '06

06 Dec '06

Hi, while pondering over the four fours problem, I wondered: Is there a function of type (a -> [b]) -> [a -> b] It looks a bit like sequence when applied in the ((->) a) Monad: sequence :: [a -> b] -> a -> [b] but I was looking for the other direction. I came up with: \g -> map (\n a -> g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas? Thanks, Joachim -- Joachim "nomeata" Breitner mail: mail(a)joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: joachimbreitner(a)amessage.de | http://www.joachim-breitner.de/ Debian Developer: nomeata(a)debian.org

6 7

Beginner: IORef constructor?
by TJ 06 Dec '06

06 Dec '06

First of all, sorry if this is a really silly question, but I couldn't figure it out from experimenting in GHCi and from the GHC libraries documentation (or Google). Is there an IORef consturctor? Or is it just internal to the Data.IORef module? I want a "global variable", so I did the following: ------ module VirtualWorld where import Data.IORef theWorld = IORef [] -- This will be writeIORef'ed with a populated list as the user modifies the world. ----- It doesn't work. GHCi says that the IORef constructor is not in scope. I did a ":module Data.IORef" and then "IORef []" and it still gives me the same error. I'm using GHC 6.6 on Windows.

5 12

There's nothing wrong with infinite types!
by Stefan O'Rear 06 Dec '06

06 Dec '06

I'm sure anyone who's used Haskell for any significant length of time has received this error message: Occurs check: cannot construct the infinite type: t = t -> t1 I for one took that as a challenge, and have implemented a type inference engine for infinite types. Expr> s (a -> b -> c) -> (a -> b) -> a -> c Expr> skk a -> a Expr> s(skk)(skk) (fix a . (a -> b)) Expr> Points of interest: * There are NO error conditions. it-unifier can assign a type to every syntactically valid expression of combinatory logic. * Typechecking is guaranteed to terminate in a linear number of steps, an (apparently) stronger guarantee than that provided by DHM. * (Mostly theoretical, since it-unify does not yet support sums or products): Fixpoint types subsume declared recursive datatypes. e.g: type List a = fix l . Either () (a,l) darcs get http://members.cox.net/stefanor/fixtypes/

2 1

Halp- haskell logic prover
by Dan Mead 06 Dec '06

06 Dec '06

Hey all, I've just finished my logic prover. I've been working on this as an undergraduate project with my advisor. Right now it only supports simple first order logic but in the spring I'll be adding predicates. Theres also a simple gui written in java 5 which is in the darcs repository. Comments are welcome! -Dan http://haskell.org/haskellwiki/Libraries_and_tools/Theorem_provers http://taz.cs.wcupa.edu/~dmead/code/halp/

1 0

HOgg 0.2.0 Released
by Conrad Parker 06 Dec '06

06 Dec '06

HOgg 0.2.0 Released ------------------- The HOgg package provides a commandline tool for manipulating Ogg files, and a corresponding Haskell library. http://snapper.kfish.org/~conrad/software/hogg/ This is the initial public release. The focus is on correctness of Ogg parsing and production. The capabilities of the hogg commandline tool are roughly on par with those of the oggz* tools[0], although hogg does not yet provide an equivalent to oggz-validate. HOgg supports chained and multiplexed Ogg bitstreams conformant with RFC3533[1]. HOgg can parse headers for CMML, FLAC, OggPCM, Speex, Theora and Vorbis media codecs, and can read and write Ogg Skeleton bitstreams. [0] Oggz: http://www.annodex.net/software/liboggz/index.html [1] RFC3533: http://www.ietf.org/rfc/rfc3533.txt Installation ------------ I am very interested in hearing about problems with building or installing the package, particularly from people who are not yet familiar with building from Haskell source. You need ghc instead of gcc; it compiles to a binary: $ ./Setup.hs configure $ ./Setup.hs build $ sudo ./Setup.hs install Building of this release has been tested with: * GHC versions 6.4 and 6.6 [2] * The Haskell build system "Cabal" versions 1.1.3, 1.1.4, 1.1.6, and the current development trunk. [3] * fps (Data.ByteString.Lazy) version 0.7, and development trunk. [4] Note that if you are using the recently-released GHC 6.6 then you will not need separate installs of Cabal or fps. You will however need to remove the word "fps" from the hogg.cabal file; see the README for details. The GHC and Cabal versions listed above span the packages available in most current distributions. I've tested on Debian unstable, Ubuntu Dapper and Ubuntu Edgy. I'm particularly interested to hear reports of build success or failure on other distributions or operating systems. [2] GHC: http://www.haskell.org/ghc/ [3] Cabal: http://www.haskell.org/cabal/ [4] fps: http://www.cse.unsw.edu.au/~dons/fps.html Usage ----- $ hogg help Usage: hogg <subcommand> [options] filename ... Commands: help Display help for a specific subcommand Reporting: info Display information about the file and its bitstreams dump Hexdump packets of an Ogg file pagedump Display page structure of an Ogg file dumpraw Dump raw (unparsed) page data Extraction: rip Rip selected logical bistreams from an Ogg file (default: all) reconstruct Reconstruct an Ogg file by doing a full packet demux Editing: merge Merge, interleaving pages in order of presentation time addskel Write a Skeleton logical bitstream Source ------ Source code is available from the darcs repository at: darcs get http://snapper.kfish.org/~conrad/software/hogg/ cheers, Conrad.

1 0

Download locations for former-base libraries?
by John Goerzen 05 Dec '06

05 Dec '06

Hi, I am working on updating and splitting things out of MissingH. MissingH is going to depend on regex-compat, HUnit, QuickCheck, and FilePath, among others. For each such library, I need to be able to tell users where they can go to download the dependency. But I'm having a lot of trouble finding canonical download locations. For instance, the homepage of regex-compat, according to http://darcs.haskell.org/packages/regex-compat/regex-compat.cabal, is http://sourceforge.net/projects/lazy-regex. But the software available for download there doesn't even provide Text.Regex. Of course, just saying "download the latest version with darcs" isn't useful, either. People that want to use my package shouldn't have to have darcs, and they also shouldn't have to fight with broken development software. Or should I be telling people to download the GHC 6.6 extralibs source? That doesn't seem quite right either; it's packaged as a tar.bz2, but what would a Windows user with HUGS do? That person probably couldn't even unpack it. Thanks, -- John

3 4

Picking out elements of a heterogenous list
by Creighton Hogg 05 Dec '06

05 Dec '06

Hi Haskell-ers, So I think I understand the idea of creating a heterogenous list using typeclasses and existentials, but I don't see how to filter the list to retrieve elements of the list that are of only one type. More concretely, taking the example here<http://haskell.org/haskellwiki/Existential_type>how could we take a list of shapes [Shape] and pull out all objects that are Squares? I don't see an obvious way this makes sense. Is there a way of doing heterogenous lists that would make this possible?

4 3

Re: haddock not finding base lib docs -- $topdir ?
by Simon Marlow 05 Dec '06

05 Dec '06

[ moving to haskell-cafe(a)haskell.org ] Claus Reinke wrote: >> This is due to the way GHC is installed on Windows, the package >> database doesn't have hardcoded pathnames, the idea being that you can >> move your GHC anywhere in the filesystem and it will still work. > > this is an essential feature (for instance, running GHC from a USB or > network drive, or just unpacking snapshots without using installers), > please do not start splicing in absolute paths! Don't worry, we don't intend to do that. >> Unfortunately this means that Haddock can't find the documentation for >> the packages. > > this part I do not understand - if GHC and ghc-pkg can find the > packages, why can't Haddock? wouldn't it just be a case of making > $topdir be in a fixed relationship to the output of "ghc --print-libdir"? well yes, but Haddock doesn't invoke 'ghc --print-libdir'. I think it would be better for ghc-pkg to hide $topdir from everyone by replacing it with its value in any ghc-pkg output. After all, $topdir is just a hack to make the GHC tree location-independent on Windows, it's not a documented feature of the package system. > or should there be a way to query ghc-pkg for the list of package > location roots? as you say, the main docs will be in a known location > relative to GHC, but perhaps docs in general should be be in a known > location relative to their packages, which ghc-pkg (or other tools for > other implementations) should be able to locate? > >> One workaround is to specify the paths by hand, using Haddock's >> --read-interface flag. You're using Haddock via Cabal though, so that >> doesn't work too well. The other workaround is to find GHC's >> package.conf file and replace the string $topdir with the literal path >> ("c:/ghc/ghc-6.6" in your case - perhaps you have to append "/doc" for >> the haddock fields, though). > > will all docs be moved into "`ghc --print-libdir`\\doc"? No. Docs can be installed wherever you like. Cabal has a policy for installation locations on Windows, which you can override if you want. > what about > local/user package databases? Same here, you can install things wherever you like. In fact, installing things inside the GHC tree isn't recommended. Cheers, Simon

1 0