- Haskell-Cafe - Haskell.org

lazy'foldl
by Sebastian Fischer 10 Feb '10

10 Feb '10

Hello, I have implemented the following function: lazy'foldl :: (a -> b -> Maybe a) -> Maybe a -> [b] -> Maybe a lazy'foldl _ Nothing _ = Nothing lazy'foldl _ m [] = m lazy'foldl f (Just y) (x:xs) = lazy'foldl f (f y x) xs After hoogling its type, I found that Control.Monad.foldM :: (a -> b -> Maybe a) -> a -> [b] -> Maybe a seems like a perfect replacement because lazy'foldl f (Just x) xs == foldM f x xs holds for all finite lists xs. Here is an inductive proof: lazy'foldl f (Just x) [] == Just x == foldM f x [] lazy'foldl f (Just x) (y:ys) == lazy'foldl f (f x y) ys (if f x y == Nothing) == lazy'foldl f Nothing ys == Nothing == Nothing >>= \z -> foldM f z ys == f x y >>= \z -> foldM f z ys == foldM f x (y:ys) lazy'foldl f (Just x) (y:ys) == lazy'foldl f (f x y) ys (if f x y == Just z) == lazy'foldl f (Just z) ys (induction) == foldM f z ys == Just z >>= \z -> foldM f z ys == f x y >>= \z -> foldM f z ys == foldM f x (y:ys) I think the above equation holds even for infinite lists xs. Both functions terminate on infinite lists, if the accumulator is eventually Nothing. Do you see any differences in terms of strictness, i.e., a counter example to the above equation that involves bottom? I don't. Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

2 1

Generate random UArray in constant memory space.
by Vasyl Pasternak 10 Feb '10

10 Feb '10

Hello Cafe, I tried to generate memory-efficient list of random numbers, so I've used uvector library for this task. But it doesn't work, it still allocates more than 6Gb of memory for the random list of 10 million elements. Here is the code: > import Text.Printf > import System.Random > import Control.Applicative > import System.Environment > import Data.Array.Vector > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) > randomListU b g size = unfoldU size gen g > where gen g = let (x, g') = randomR b g > in JustS (x :*: g') > main = do > [size] <- map read <$> getArgs > let ints = randomListU (-10, 10) (mkStdGen 1) size > printf "%d\n" (sumU ints) Could someone give a hint, how to implement this function in constant memory space? Thank you in advance. Best regards, Vasyl Pasternak

4 9

Two GET HTTP requests
by Chris Eidhof 10 Feb '10

10 Feb '10

Hi everyone, I'm trying to do a number of successive HTTP requests in one program. Here's what I tried: Approach 1: I used the 'download' package, which failed to install on OS X. It fails with "error: libio.h: No such file or directory". Approach 2: I installed the 'download-curl' package, and tried again. This seems to fail on the following example: > import Network.Curl.Download > > main = do x <- openURI "http://haskell.org" > y <- openURI "http://haskell.org/hoogle" > return () If I put a print statement around the second line of the do-statement it looks like openURI never returns. Approach 3: I used the simpleHTTP function from the HTTP package. This crashed, after I dug a little deeper into the code, it threw an error on calling the parseURI function (openFile: no such file exists). I installed the latest network package and upgraded my HTTP package, and the parseURI error went away. I felt like I was almost there, and tried the following: > simpleHTTP (getRequest "http://haskell.org") This failed with just the text "Bus error". I searched the HTTPBis git repository, but couldn't find the text "Bus error". I don't have a clue of how to fix this. I'm a bit stuck here, I would love to help fix the errors, but don't know what would be the best place to begin. If anyone can point me in the right direction, I will try to patch at least one of these packages. Thanks, -chris

4 8

Lazy language on JVM/CLR
by Tony Morris 10 Feb '10

10 Feb '10

I have hypothesised a pure, lazy language on the JVM and perhaps the .NET CLR with FFI to .NET/Java libraries. I foresee various problems but none that are catastrophic; just often requiring a compromises, sometimes very unattractive compromises. I have authored several libraries in the same vain as pure, lazy programming to run on the JVM in Java and Scala programming languages. I expect others have forethought and perhaps even experimented with such a language. Are there any dangers to be wary of that undo the entire endeavour? Thanks for any insights. -- Tony Morris http://tmorris.net/

9 9

Jobs
by Roderick Ford 10 Feb '10

10 Feb '10

We need two developers at the company I work for; that is, I am NOT a recruiter. My boss is asking me to search for developers for me to work with ... like minded, haskell loving, driven, c/c++ (c# if we have to) for an INITIALLY c# full-time salaried position in Arizona (or FL or UT). He is open to starting new projects using Haskell, where applicable. So, he is involving me in the interview process, and I've been less than pleased with candidate selection so far. I told him we need to find people that see the beauty of mathematics and Haskell. If you have a resume you want me to forward on, reply to me directly and I will forward on through the review process. Here is a clip from posting 1 (don't take too literally): Software Engineer with strong 'Design, Programming, Debugging' experience Required Experience 3+yrs MS C# *AND* C++ MS SQL Server MS ASP.NET MS SQL Applicants must have at least 3 years practical work experience designing and building commercial software products that have shipped on the Windows OS platform. Requires proven experience building Web GUI on Windows platform, familiarity with distributed programming and networking. Must also be able to write and debug SQL Stored Procedures. Developer will be required to take ownership of the assigned modules through design, code & unit test. Past team lead experience would be valuable. Familiarity with gcc and Linux / Unix programming would be a plus. 4 year degree in a Computer Science related field with at least 5-7 years of experience in a software development environment or similar combination of education/work experience. This position is available in the following offices: Scottsdale, Arizona Provo, Utah Melbourne, Florida Here is a clip from posting 2: Job Description As a Senior C# - Asp.net Software Engineer in this position you will operate within a group of engineers, engaged in product design and implementation of enterprise applications. This role has a very high level of technical and product knowledge spanning multiple development technologies and target platforms. The Senior Software Engineer operates unsupervised and is a self-starter. Essential Duties and Responsibilities: Performs OOD, implementation and maintenance for products composed with a variety of technologies, mostly for Windows platforms but also Linux and other platforms Provides expertise for multiple software layers and levels of abstraction: UI, business layer, database, and distributed operations. Builds a tactical consensus with the development team whilst demonstrating strong technical leadership skills Experience working in a scrum agile environment a plus Performs highly complex product design activities which may require extensive research and analysis Performs complex bug verification, release testing and beta support for assigned products Researches problems discovered by QA or product support and identifies solutions to the problems Conducts unit testing and integration testing for functionality and performance limits In absence of product architects, may serve as a product architect Researches and understands non-functional requirements beyond the marketing requirements for a product Researches new technology or development tools to remain informed of current technology Required Skills Advanced technical knowledge in software development methodologies, design and implementation in C#. Expert analytical and design skills at multi-product/multi-environment level. Understands cross-platform and/or internationalisation development. In-depth experience in research and analysis, project planning and implementation. Excellent understanding of entire development process, including specification, documentation and quality assurance. Aware of business issues as they impact overall project plans. Recognised reference and central point for technical issues across groups and products. Strong communications and interpersonal skills. Advanced PC skills. Required Experience A university degree in computer science or software engineering, preferably a masters or higher, is desireable. Requires 10 to 15 years of experience in product design Good knowledge of .Net, and ASP.NET, for C# developers. Minimum 5 Years Experience of C# language and Asp.net

1 0

Navigating Graphs
by Matthias Görgens 09 Feb '10

09 Feb '10

Using something like zippers it is easy to navigate an acyclic graph in O(1) operations per arc you follow. Inspired by Chris Okasaki's work on queues I wondered if there is a similar approach to navigating cyclic graphs. If the graph you are navigating is static (i.e. does not have to support addition or removal of vertices in any reasonable amount of time), I guess you can get away with "Tying the know" (http://www.haskell.org/haskellwiki/Tying_the_Knot) But is there a technique that allows navigation, insertion and removal at focus in (at least amortised) O(1) operations each? As a generalisation being able to have multiple points of focus (in an acyclic graph for a start) would also be interesting. Any thoughts?

1 0

Re: [Haskell-cafe] Generate random UArray in constant memory space.
by Daniel Fischer 09 Feb '10

09 Feb '10

Am Tuesday 09 February 2010 19:19:18 schrieben Sie: > Daniel, > > I've just run venum2 program locally and here is my results: > > $ ./venum2 10000000 +RTS -s > ./venum2 10000000 +RTS -s > 50000005000000 > 22,736 bytes allocated in the heap > 688 bytes copied during GC > 17,184 bytes maximum residency (1 sample(s)) > 19,680 bytes maximum slop > 1 MB total memory in use (0 MB lost due to fragmentation) > > $ ./venum2 1000000000 +RTS -s > ./venum2 1000000000 +RTS -s > 500000000500000000 > 24,152 bytes allocated in the heap > 688 bytes copied during GC > 17,184 bytes maximum residency (1 sample(s)) > 19,680 bytes maximum slop > 1 MB total memory in use (0 MB lost due to fragmentation) > > So my PC shows that there is constant memory allocation. Maybe I'm > doing something wrong ? Unlikely. However, I notice that you seem to have a 64-bit system. I don't know the details, but usually those have more registers than a 32- bit system, so you can get more complicated loops to run completely in the registers. I think that's what happens here, enumFromToU' is just complicated enough to not run in the registers on my 32-bit system, but still runs in the registers on your 64-bit system. The PRNG code is too complicated (too many temporary variables) to run in the registers on either system (BTW, have you tried it with the specialised PRNG code in the source file? I'm not sure whether that might be just small enough to run in the registers on a 64-bit system.). > > 2010/2/9 Daniel Fischer <daniel.is.fischer(a)web.de>: > > Am Tuesday 09 February 2010 15:43:13 schrieben Sie: > >> Update: > >> > >> I've implemented `enumFromToU` through `unfoldU`: > >> > enumFromToU' from to = unfoldU (to - from) f from > >> > where f i = let i' = i + 1 in JustS (i' :*: i') > >> > >> This code behaves similarly to `enumFromToU` (i.e. constantly uses > >> ~25 kb of memory, runs in the same time as above). > > > > Wait, > > > > $ cat venum2.hs > > module Main (main) where > > > > import Text.Printf > > import Control.Applicative > > import System.Environment > > import Data.Array.Vector > > > > main = do > > [size] <- map read <$> getArgs > > let ints = enumFromToU' 0 size :: UArr Int > > printf "%d\n" (sumU ints) > > > > enumFromToU' from to = unfoldU (to - from) f from > > where f i = let i' = i + 1 in JustS (i' :*: i') > > > > $ ghc -O2 --make venum2 > > [1 of 1] Compiling Main ( venum2.hs, venum2.o ) > > Linking venum2 ... > > $ ./venum2 +RTS -sstderr -RTS 1000000 > > ./venum2 1000000 +RTS -sstderr > > 1784293664 > > 48,256,384 bytes allocated in the heap > > 6,256 bytes copied during GC > > 26,804 bytes maximum residency (1 sample(s)) > > 25,524 bytes maximum slop > > 1 MB total memory in use (0 MB lost due to > > fragmentation) > > > > $ ./venum2 +RTS -sstderr -RTS 10000000 > > ./venum2 10000000 +RTS -sstderr > > -2004260032 > > 481,937,552 bytes allocated in the heap > > 19,516 bytes copied during GC > > 26,804 bytes maximum residency (1 sample(s)) > > 25,512 bytes maximum slop > > 1 MB total memory in use (0 MB lost due to > > fragmentation) > > > > So we have constant memory, but linear allocation, just like with the > > random numbers. > > > > With enumFromToU, also the allocation is constant, so unfoldU > > allocates, enumFromToU not. > > > >> So the question is why random number list generator eats O(n) memory > >> ? > > > > It doesn't, not here, at least. Using System.Random, the allocation > > figures are about ten times as high, but the residency is about the > > same. Putting the PRNG code in the same file and tweaking things a bit > > (eliminating all intermediate Integers, e.g.), I get > > > > $ cat ran2Vec.hs > > {-# LANGUAGE BangPatterns #-} > > module Main (main) where > > > > import Text.Printf > > import Control.Applicative > > import System.Environment > > import Data.Array.Vector > > > > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) > > randomListU b@(l,h) g size = unfoldU size gen g > > where > > !k = h-l+1 > > !b' = 2147483561 `rem` k > > gen !g = let (!x, !g') = stdNext g > > in JustS ((l+ (x+b') `rem` k) :*: g') > > > > main = do > > [size] <- map read <$> getArgs > > let ints = randomListU (-10, 10) (mkStdGen 1) size > > printf "%d\n" (sumU ints) > > > > data StdGen = StdGen {-# UNPACK #-} !Int {-# UNPACK #-} !Int > > > > mkStdGen :: Int -> StdGen > > mkStdGen s > > | s < 0 = mkStdGen (-s) > > | otherwise = StdGen (s1+1) (s2+1) > > where > > (q, s1) = s `divMod` 2147483562 > > s2 = q `mod` 2147483398 > > > > {-# INLINE stdNext #-} > > stdNext :: StdGen -> (Int, StdGen) > > -- Returns values in the range stdRange > > stdNext (StdGen s1 s2) = z' `seq` g' `seq` (z', g') > > where > > !g' = StdGen s1'' s2'' > > !z' = if z < 1 then z + 2147483562 else z > > !z = s1'' - s2'' > > > > !k = s1 `quot` 53668 > > !s1' = 40014 * (s1 - k * 53668) - k * 12211 > > !s1'' = if s1' < 0 then s1' + 2147483563 else s1' > > > > !k' = s2 `quot` 52774 > > !s2' = 40692 * (s2 - k' * 52774) - k' * 3791 > > !s2'' = if s2' < 0 then s2' + 2147483399 else s2' > > $ ghc -O2 -funbox-strict-fields -funfolding-use-threshold=16 --make > > ran2Vec -o ran2AVec5 > > Linking ran2AVec5 ... > > $ ./ran2AVec5 +RTS -sstderr -RTS 10000000 > > ./ran2AVec5 10000000 +RTS -sstderr > > 5130 > > 521,828,888 bytes allocated in the heap > > 8,664 bytes copied during GC > > 26,788 bytes maximum residency (1 sample(s)) > > 25,636 bytes maximum slop > > 1 MB total memory in use (0 MB lost due to > > fragmentation) > > > > nearly the same allocation figures as for the *much* simpler > > enumFromToU', and it's about ten times as fast as System.Random. > >

2 1

Strange Haddock output
by Sean Leather 09 Feb '10

09 Feb '10

I was browsing Hackage pointlessly and came across what appears to be strange Haddock formatting here: http://hackage.haskell.org/packages/archive/pointless-haskell/0.0.3/doc/htm… The following source -- | Polytypic 'Prelude.Functor' class for functor representations class Functor (f :: * -> *) where fmap :: Fix f -- ^ For desambiguation purposes, the type of the functor must be passed as an explicit paramaeter to 'fmap' -> (x -> y) -> Rep f x -> Rep f y -- ^ The mapping over representations produces the following view from the browser class Functor f where Polytypic Prelude.Functor class for functor representations Methods fmap :: => Fix f -> x -> y -> Rep f x The mapping over representations -> Rep f y with the Haddock 2.6.0 on Hackage. There seems to be an extraneous => in the signature of fmap, and the comment on Fix f does not show up. Sean

2 2

automatically exclude unused modules at compile time
by Hong Yang 09 Feb '10

09 Feb '10

When I turned on "-Wall" knob at compile time, I got a message: Warning: Module `System.Cmd' is imported, but nothing from it is used, except perhaps instances visible in `System.Cmd' To suppress this warning, use: import System.Cmd() Then I did four experiments as follows at compile time: 1) import System.Environment 2) import System.Environment() 3) import System.Environment(only the functions I used) 4) -- import System.Environment It turned out that case 1-3) have the size after compilation, and that case 4) has smaller size than the others. Can we make GHC a little bit more intelligent to automatically exclude unused modules at compile time as in case 4)? (Am I just too lazy to add several dashes?) Thanks, Hong

2 2

Re: [Haskell-cafe] Generate random UArray in constant memory space.
by Daniel Fischer 09 Feb '10

09 Feb '10

Am Tuesday 09 February 2010 15:43:13 schrieben Sie: > Update: > > I've implemented `enumFromToU` through `unfoldU`: > > enumFromToU' from to = unfoldU (to - from) f from > > where f i = let i' = i + 1 in JustS (i' :*: i') > > This code behaves similarly to `enumFromToU` (i.e. constantly uses ~25 > kb of memory, runs in the same time as above). Wait, $ cat venum2.hs module Main (main) where import Text.Printf import Control.Applicative import System.Environment import Data.Array.Vector main = do [size] <- map read <$> getArgs let ints = enumFromToU' 0 size :: UArr Int printf "%d\n" (sumU ints) enumFromToU' from to = unfoldU (to - from) f from where f i = let i' = i + 1 in JustS (i' :*: i') $ ghc -O2 --make venum2 [1 of 1] Compiling Main ( venum2.hs, venum2.o ) Linking venum2 ... $ ./venum2 +RTS -sstderr -RTS 1000000 ./venum2 1000000 +RTS -sstderr 1784293664 48,256,384 bytes allocated in the heap 6,256 bytes copied during GC 26,804 bytes maximum residency (1 sample(s)) 25,524 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) $ ./venum2 +RTS -sstderr -RTS 10000000 ./venum2 10000000 +RTS -sstderr -2004260032 481,937,552 bytes allocated in the heap 19,516 bytes copied during GC 26,804 bytes maximum residency (1 sample(s)) 25,512 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) So we have constant memory, but linear allocation, just like with the random numbers. With enumFromToU, also the allocation is constant, so unfoldU allocates, enumFromToU not. > > So the question is why random number list generator eats O(n) memory ? It doesn't, not here, at least. Using System.Random, the allocation figures are about ten times as high, but the residency is about the same. Putting the PRNG code in the same file and tweaking things a bit (eliminating all intermediate Integers, e.g.), I get $ cat ran2Vec.hs {-# LANGUAGE BangPatterns #-} module Main (main) where import Text.Printf import Control.Applicative import System.Environment import Data.Array.Vector randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) randomListU b@(l,h) g size = unfoldU size gen g where !k = h-l+1 !b' = 2147483561 `rem` k gen !g = let (!x, !g') = stdNext g in JustS ((l+ (x+b') `rem` k) :*: g') main = do [size] <- map read <$> getArgs let ints = randomListU (-10, 10) (mkStdGen 1) size printf "%d\n" (sumU ints) data StdGen = StdGen {-# UNPACK #-} !Int {-# UNPACK #-} !Int mkStdGen :: Int -> StdGen mkStdGen s | s < 0 = mkStdGen (-s) | otherwise = StdGen (s1+1) (s2+1) where (q, s1) = s `divMod` 2147483562 s2 = q `mod` 2147483398 {-# INLINE stdNext #-} stdNext :: StdGen -> (Int, StdGen) -- Returns values in the range stdRange stdNext (StdGen s1 s2) = z' `seq` g' `seq` (z', g') where !g' = StdGen s1'' s2'' !z' = if z < 1 then z + 2147483562 else z !z = s1'' - s2'' !k = s1 `quot` 53668 !s1' = 40014 * (s1 - k * 53668) - k * 12211 !s1'' = if s1' < 0 then s1' + 2147483563 else s1' !k' = s2 `quot` 52774 !s2' = 40692 * (s2 - k' * 52774) - k' * 3791 !s2'' = if s2' < 0 then s2' + 2147483399 else s2' $ ghc -O2 -funbox-strict-fields -funfolding-use-threshold=16 --make ran2Vec -o ran2AVec5 Linking ran2AVec5 ... $ ./ran2AVec5 +RTS -sstderr -RTS 10000000 ./ran2AVec5 10000000 +RTS -sstderr 5130 521,828,888 bytes allocated in the heap 8,664 bytes copied during GC 26,788 bytes maximum residency (1 sample(s)) 25,636 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) nearly the same allocation figures as for the *much* simpler enumFromToU', and it's about ten times as fast as System.Random. > > Regards, > Vasyl Pasternak > > 2010/2/9 Vasyl Pasternak <vasyl.pasternak(a)gmail.com>: > > Sorry, maybe I should ask more clearer. > > > > I've looked at dons article "Haskell as fast as C"[1], and tried to > > implement similar algorithm but for list of random numbers. > > > > Please look at code: > >> import Text.Printf > >> import Control.Applicative > >> import System.Environment > >> import Data.Array.Vector > >> > >> main = do > >> [size] <- map read <$> getArgs > >> let ints = enumFromToU 0 size :: UArr Int > >> printf "%d\n" (sumU ints) > > > > This code runs in constant space (on my pc ~25kb allocates on the > > heap) regardless of array size. So I tried to achieve similar with > > random list, just to replace `enumFromToU` with my own list generator. > > > > So the question - is it possible to implement random list similary to > > enumFromToU? > > > > > > [1]http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-workin > >g-at-a-high-altitude-for-low-level-performance/ > > > > Thank you, > > Vasyl Pasternak > > > > 2010/2/9 Daniel Fischer <daniel.is.fischer(a)web.de>: > >> Am Dienstag 09 Februar 2010 13:18:23 schrieb Vasyl Pasternak: > >>> Hello Cafe, > >>> > >>> I tried to generate memory-efficient list of random numbers, so I've > >>> used uvector library for this task. But it doesn't work, > >>> it still allocates more than 6Gb of memory for the random list of 10 > >>> > >>> million elements. Here is the code: > >> > >> Hmm, > >> > >> $ ghc -O2 --make ranVec > >> [1 of 1] Compiling Main ( ranVec.hs, ranVec.o ) > >> Linking ranVec ... > >> $ ./ranVec 10000000 +RTS -sstderr > >> 5130 > >> 4,919,912,080 bytes allocated in the heap > >> 883,256 bytes copied during GC > >> 26,896 bytes maximum residency (1 sample(s)) > >> 25,620 bytes maximum slop > >> 1 MB total memory in use (0 MB lost due to > >> fragmentation) > >> > >> maximum residency is just eight bytes more than for 100,000 or > >> 1,000,000 numbers. I think that is constant space. > >> > >> The ~5 GB total allocation is sequential, ten million new StdGens are > >> produced and allocated, then immediately garbage collected. I see no > >> problem (except that StdGen is slow, e.g. the Mersenne twister is > >> much faster [and allocates less, but still linear in size]). > >> > >>> > import Text.Printf > >>> > import System.Random > >>> > import Control.Applicative > >>> > import System.Environment > >>> > import Data.Array.Vector > >>> > > >>> > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) > >>> > randomListU b g size = unfoldU size gen g > >>> > where gen g = let (x, g') = randomR b g > >>> > in JustS (x :*: g') > >>> > > >>> > main = do > >>> > [size] <- map read <$> getArgs > >>> > let ints = randomListU (-10, 10) (mkStdGen 1) size > >>> > printf "%d\n" (sumU ints) > >>> > >>> Could someone give a hint, how to implement this function in > >>> constant memory space? > >>> > >>> Thank you in advance. > >>> > >>> Best regards, > >>> Vasyl Pasternak

1 0