- Haskell-Cafe - Haskell.org

Profiling help (Warning: Euler spoilers)
by Louis Wasserman 04 Mar '10

04 Mar '10

James, Which version of Control.Monad.State are you importing? If you're just importing vanilla Control.Monad.State, that's actually sending you to Control.Monad.State.Lazy. Using Control.Monad.State.Strict might solve your problems, srsly. Laziness can result in epically failing memory leaks. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

2 3

ANN: iteratee-parsec 0.0.2
by Maciej Piechotka 04 Mar '10

04 Mar '10

Iteratee-parsec is a library which allows to have a parsec (3) parser in IterateeG monad. It contains 2 implementations: - John Lato's on public domain. It is based on monoid and design with short parsers in mind. - Mine on MIT. It is based on single-linked mutable list. It seems to be significantly faster for larger parsers - at least in some cases - but it requires a monad with references (such as for example IO or ST). Version 0.0.2 does not differ much from 0.0.1 except that it is up-to-date with parsec 3.1.0 (version 0.0.1 is not). Regards

1 0

type class constraints headache
by muneson 04 Mar '10

04 Mar '10

When writing a command-line interface I ran into type class conflicts I don't understand. Could anyone explain why ghc 6.10.4 compiles this > methods :: (Eq a) => [(String, a)] > methods = > [ ("method1", undefined ) > , ("method2", undefined) > ] but not the following? > methods :: (Eq a) => [(String, a)] > methods = > [ ("method1", undefined ) > , ("method2", undefined) > ] > > enumerateMethodNames :: [String] > enumerateMethodNames = map fst methods thanks, Marcus -- View this message in context: http://old.nabble.com/type-class-constraints-headache-tp27752745p27752745.h… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 7

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 04 Mar '10

04 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 04 Mar '10

04 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 04 Mar '10

04 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 04 Mar '10

04 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 04 Mar '10

04 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