March 2010 - Haskell-Cafe

idioms ... for using Control.Applicative.WrapMonad or Control.Arrow.Kleisli?
by Nicolas Frisby 04 Mar '10

04 Mar '10

Each time I find myself needing to use the wrapping functions necessary for this embeddings, I grumble. Does anyone have a favorite use-pattern for ameliorating these quickly ubiquitous conversions? For runKleisli, I was considering something like okKleisli :: (Control.Arrow.Kleisli m a b -> Control.Arrow.Kleisli m' a' b') -> (a -> m b) -> (a' -> m' b') onKleisli f = Control.Arrow.runKleisli . f . Control.Arrow.Kleisli but haven't really tested its usefulness. My most frequent use cases usually include Arrow.first, Arrow.second, &&&, ***, or +++. E.g. somefun :: (Monad m, Num a) => (a, d) -> m (a, d) somefun = onKleisli Control.Arrow.first (\ a -> return (a + 1)) Perhaps a Control.Arrow.Kleisli, which would export (same-named) Kleisli specializations of all the Control.Arrow methods? And an analogous Control.Applicative.Monad? (Data.Traversable does this a little bit to specialize its interface for monads, such as Data.Traversable.sequence.) While writing this, I realized that you can't leave the Arrow-ness of Kleisli arrows implicit, since (->) a (m b) is two kinds of arrows depending on context -- which is precisely what the Kleisli newtype resolves. So I'm not seeing a reason to bring up the 'class Applicative m => Monad m where' dispute. Thanks for your time.

2 1

Re: [Haskell-cafe] Free theorem - what do we need it for
by Janis Voigtländer 03 Mar '10

03 Mar '10

Maciej Piechotka wrote: > I am afraid that I fail to see practical benefits (I mean that I don't > know all implication not that I think there is no benefits). > What are the benefits of free theorem except large chance that data will Lots of applications. See page 34 (along with the references starting from page 218) of http://www.iai.uni-bonn.de/~jv/ppl2010-slides.pdf for a list of some of them. Ciao, Janis -- Jun.-Prof. Dr. Janis Voigtländer http://www.iai.uni-bonn.de/~jv/ mailto:jv@iai.uni-bonn.de

1 0

ANN: uuid-0.1.2
by Mark Lentczner 03 Mar '10

03 Mar '10

Antione and I are please to announce the release of uuid-0.1.2. CHANGES: - added functions toByteString and fromByteString - added 'nil' UUID - added unit tests and benchmarks, built when configured -ftest - major speed up of to/from functions (as well as in general) - added version-3 generation (deterministic based on MD5) - major changes to internal representation - now uses four strict Word32 values - internal ByteSource classes for easy construction (see Builder.hs) - Storable instance now stores in memory as system libraries in C do: 16 bytes derived from the network order of the fields, no matter what the host native endianess is. - fixed bugs in V1 time and clock stepping, and V1 generated values - builds cleanly under GHC's -Wall - added CHANGES file String conversions were sped up 4x to 7x! - Mark Mark Lentczner (MtnViewMark) http://www.ozonehouse.com/mark/

2 2

Profiling help (Warning: Euler spoilers)
by James Jackson 03 Mar '10

03 Mar '10

I have written the program below, which solves problem 14 from Project Euler, which asks us to find the hailstone number below 1 million that takes the longest to get to 1. The program solves the problem using dynamic programming using a Data.Map. It completes in under a minute (barely), but allocates a ridiculous amount of memory and actually runs slower than the naive one-liner it was supposed to replace. I have an intuition on what the problem is, but would like to verify it by profiling. Unfortunately, I don't know enough about how profiling works in GHC to diagnose the problem. Hopefully the Cafe can help. Here's the code. scratch.hs: This is the main program, which just calls the problemFourteen function. The EP datatype just contains an int representing the problem number and an (IO ()) which prints out the solution --------------------------------------------------------------------------------------------------------------------------- import Euler1to20 -- contains problems 1 through 20 import Euler -- Contains various utility functions including the EC type which represents Euler Problems main = proc where (EP num proc) = problemFourteen --------------------------------------------------------------------------------------------------------------------------- Euler1to20.hs: contains the following lines, among others --------------------------------------------------------------------------------------------------------------------------- problemFourteen = EP 14 $ print $ (key, fromJust $ findIndex (==key) keys) where (keys, results) = runState (mapM findChainLength [1..10^6]) $ M.fromList [(1,1)] key = maximum keys findChainLength::Integer->State (M.Map Integer Integer) Integer findChainLength n = do m <- get case M.lookup n m of Nothing -> let nextLink = if even n then div n 2 else 3*n+1 in do len <- liftM (1+) (findChainLength nextLink) m2 <- get m2 `seq` put (M.insert n len m2) return len Just n'-> return n' --------------------------------------------------------------------------------------------------------------------------- My guess is that the problem is in the recursive call to findChainLength, which is not in tail position. I think that this is causing the code to keep too many old copies of the map around. Before I go rewriting everything, however, I'd like to verify that this is indeed the problem, so the next step is to compile and run with profiling turned on. After quickly looking at the Real World Haskell chapter on profiling, I do the following. Compiling and running: --------------------------------------------------------------------------------------------------------------------------- ghc -prof --make -auto-all -fforce-recomp scratch.hs [1 of 3] Compiling Euler ( Euler.hs, Euler.o ) [2 of 3] Compiling Euler1to20 ( Euler1to20.hs, Euler1to20.o ) [3 of 3] Compiling Main ( scratch.hs, scratch.o ) Linking scratch ... ./scratch +RTS -sstderr -hc -p -K100M (525,837798) 9,503,907,112 bytes allocated in the heap 42,785,764,376 bytes copied during GC (scavenged) 15,697,610,688 bytes copied during GC (not scavenged) 421,548,032 bytes maximum residency (193 sample(s)) 17787 collections in generation 0 (650.00s) 193 collections in generation 1 (1748.37s) 782 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 18.68s ( 19.19s elapsed) GC time 2398.37s (2401.47s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 50.48s ( 50.50s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 2467.53s (2471.17s elapsed) %GC time 97.2% (97.2% elapsed) Alloc rate 508,742,769 bytes per MUT second Productivity 0.8% of total user, 0.8% of total elapsed --------------------------------------------------------------------------------------------------------------------------- I can see from the above that the maximum resident memory at one time is 782Mb, which seems excessive, since I don't expect the Map to contain more than around 2M entries. Also, I had to use "-K 100M" to increase the stack space or the program bombs out with a stack overflow exception. Since I compiled with profiling information, running the program produced the following scratch.prof: --------------------------------------------------------------------------------------------------------------------------- Wed Mar 3 19:41 2010 Time and Allocation Profiling Report (Final) scratch +RTS -sstderr -hc -p -K100M -RTS total time = 18.68 secs (934 ticks @ 20 ms) total alloc = 5,327,238,992 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc findChainLength Euler1to20 93.8 90.5 CAF Euler1to20 5.2 8.0 problemFourteen Euler1to20 1.0 1.5 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.0 100.0 100.0 CAF Main 212 2 0.0 0.0 0.0 0.0 main Main 218 1 0.0 0.0 0.0 0.0 CAF GHC.Handle 164 4 0.0 0.0 0.0 0.0 CAF Euler1to20 139 21 5.2 8.0 100.0 100.0 findChainLength Euler1to20 220 3168610 93.8 90.5 93.8 90.5 problemFourteen Euler1to20 219 1 1.0 1.5 1.0 1.5 CAF Control.Monad.State.Lazy 137 1 0.0 0.0 0.0 0.0 --------------------------------------------------------------------------------------------------------------------------- The above tells me that almost all the CPU time and memory allocation happens in findChainLength, but that isn't really a surprise. I think the next step is to start adding cost centers to get a more detailed profile, but here is where I hit the end of my ghc profiling knowledge. Can anyone help with some general strategies for how to use the profiling tools in GHC to track this down? Of course once the culprit has been found, I have to figure out what to *do* about it, but one thing at a time... James

1 0

Free theorem - what do we need it for
by Maciej Piechotka 03 Mar '10

03 Mar '10

Some time ago I get knew about free theorem that states (omitting undefined & co.) that there is 1 haskell function forall a. a -> a. The property seems to be workaround by Typeable but it stills not work for all types so it cannot be used in, for example, Monad or Functor. I am afraid that I fail to see practical benefits (I mean that I don't know all implication not that I think there is no benefits). What are the benefits of free theorem except large chance that data will obey he functor/monad laws? I.e. what advantage it gives over the 'reflection' from other languages? Regards

1 0

Has anybody translated Douglas Hofstadter's Scientific American articles introducting Scheme to a general audience into Haskell?
by DekuDekuplex＠Yahoo.com 03 Mar '10

03 Mar '10

There is an interesting, if somewhat dated, suggestion on "Lambda the Ultimate" (see http://lambda-the-ultimate.org/node/1748) that "someone translate Doug Hofstadter's Scientific American columns introducing Scheme to a general audience into Haskell." (I came across this link while adding full titles and links to the HaskellWiki "Books and tutorials" page (see http://www.haskell.org/haskellwiki/Books_and_tutorials) where I clicked on the link to "Tutorials" (see http://www.haskell.org/haskellwiki/Tutorials) which contained a link to a "Haskell vs. Scheme" (see http://www.reddit.com/r/programming/tb/nq1k) article, which described the post containing the suggestion.) According to a comment by Ehud Lamm (see http://lambda-the-ultimate.org/node/1748#comment-21292) on the above post, the columns are in Hoftstadter's book _Metamagical Themas: Questing For The Essence Of Mind And Pattern_ [1] (see http://www.amazon.com/Metamagical-Themas-Questing-Essence-Pattern/dp/046504…) Has anybody translated Hofstadter's articles from Scheme into Haskell? -- Benjamin L. Russell [1] Hofstadter, Douglas. _Metamagical Themas: Questing For The Essence Of Mind And Pattern._ New York: Basic Books, 1996. <http://www.amazon.com/Metamagical-Themas-Questing-Essence-Pattern/dp/046504…>. -- Benjamin L. Russell / DekuDekuplex at Yahoo dot com http://dekudekuplex.wordpress.com/ Translator/Interpreter / Mobile: +011 81 80-3603-6725 "Furuike ya, kawazu tobikomu mizu no oto." -- Matsuo Basho^

2 2

how to get a string from file
by Pradeep Wickramanayake 03 Mar '10

03 Mar '10

getItemFile :: IO String getItemFile test = do test <- readFile "input.txt" return test this is the program I did to take a file and get all the data from that file to a string. Can someone help me. I get this error Type error in explicitly typed binding *** Term : getItemFile *** Type : a -> IO [Char] *** Does not match : IO String What I need is to get the file to a string and then get it to a tuple by checking each places where the file contain a blank space Please help me Thanks

3 2

minimal interface
by Sean McLaughlin 03 Mar '10

03 Mar '10

Hello, I have a midsize program, and would like to simplify the module interfaces for my own sanity. I know there are tools to check for extraneous imports, but is there something similar for exports? For instance, if module A exports f, but A.f is never used in my compiled program, I would like to be warned of this fact. Thanks, Sean

3 4

segmentation fault with ghc-6.10.4 on linux-x86_x64
by Wim Vanderbauwhede 03 Mar '10

03 Mar '10

Hello, I'm writing a compiler and it segfaults when compiled with ghc-6.10.4 on linux-x86_x64. It runs fine when compiled with ghc-6.10.4 on Mac OS X 10.5 (64-bit Intel) and with ghc-6.8.2 on Mac OS X 10.4 (32-bit PPC). I use the Haskell platform, the ghc -v output is Glasgow Haskell Compiler, Version 6.10.4, for Haskell 98, stage 2 booted by GHC version 6.8.2 Using package config file: /usr/local/lib/ghc-6.10.4/./package.conf Using package config file: /users/wim/.ghc/x86_64-linux-6.10.4/package.conf hiding package base-3.0.3.1 to avoid conflict with later version base-4.1.0.0 hiding package network-2.2.1.2 to avoid conflict with later version network-2.2.1.4 hiding package time-1.1.2.4 to avoid conflict with later version time-1.1.4 wired-in package ghc-prim mapped to ghc-prim-0.1.0.0 wired-in package integer mapped to integer-0.1.0.1 wired-in package base mapped to base-4.1.0.0 wired-in package rts mapped to rts-1.0 wired-in package haskell98 mapped to haskell98-1.0.1.0 wired-in package syb mapped to syb-0.1.0.1 wired-in package template-haskell mapped to template-haskell-2.3.0.1 wired-in package dph-seq mapped to dph-seq-0.3 wired-in package dph-par mapped to dph-par-0.3 The offending code is (simplified) mapM emit (sc_args sc) with sc::ServiceCall data ServiceCall = MkServiceCall { sc_args::[Expr], ... } data Expr = PureE (PString String) | ... and emit defined via a type class EmitG: emitExpr (PureE e) = emit e instance EmitG Expr where emit = emitExpr emitPureExpr (PString s) = return $ show s instance EmitG PureExpr where emit = emitPureExpr So it actually maps "show" over a list of strings. The compiler parses a test program, the segfault occurs when emitting code for lines like ImgBlock() img1 = img.in("img.raw"); (a "service call" in my language) Replacing the string by a number of any other type of the AST makes no difference. It looks like a bug in ghc's memory allocation. Any suggestions on how to debug this? Thanks! Wim

2 1

how to send a string to a tuple
by Pradeep Wickramanayake 03 Mar '10

03 Mar '10

Hi I have taken a string output from a file But I want to send that string to another function which will convert in to a tuple Can someone teach me please

2 1