- Haskell-Cafe - Haskell.org

Parody of Darcs patch theory from 1981
by Paul Johnson 02 Mar '08

02 Mar '08

I was looking through my old copy of "The Devil's DP Dictionary" by Stan Kelly-Bootle, and came across the entry for Stepwise Refinement. I thought "I've seen this before: this is a parody of Darcs patch theory". It included the Null patch, chains of patches, inverse patches, and pseudo-inverse patches. But the book was published in 1981. I've got the pages scanned, but I can't upload them to Wikimedia because they are still in copyright. However I'm quite sure that limited distribution would fall into "fair use" (non-commercial, small part of work, no impact on market, academic relevance). The total file size is about 520kBytes. Assuming people would like to see them, does anyone have any ideas beyond "email to requestors"? Paul.

3 3

A mini haskell (in 244 lines of python)
by Tim Newsham 02 Mar '08

02 Mar '08

For education and fun I wrote a small untyped non-strict lambda calculus evaluator in python. One of the goals was to keep it fairly small and simple, and to do most of the work in the implemented scripting language itself. For that reason, I added macros to allow things like "let" and "letrec" to be defined as syntactic sugar easily outside of the evaluation engine itself. The result is 244 lines of python, a small prelude that implements tuples, lists and the state monad, and some small example scripts. The prelude and scripts are heavily influenced by Haskell, the main differences being a much simpler syntax, lack of pattern matching and lack of a type system. Data structures aren't supported but are implemented fairly easily using lambda expressions as described in http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-Eff… This is all available at http://www.thenewsh.com/%7Enewsham/lambda/ as extracted package and .tgz. The README file has documentation including small examples. Accompanying scripts provide more complete examples, such as: [WITHLIST [LET from2 (iter (add 1) 2) [LET primes (nubBy (\x \y (eq (mod y x) 0)) from2) (traceList Val (take 10 primes)) ]]] which calculates the first 10 primes. Exercise to the reader: I bet the evaluator could all be written much more compactly in Haskell. Tim Newsham http://www.thenewsh.com/~newsham/

1 0

Generating a random list
by Milos Hasan 02 Mar '08

02 Mar '08

Hi, so let's say I want to generate a list of N random floats. The elegant way of doing it would be to create an infinite lazy list of floats and take the first N, but for N = 1,000,000 or more, this overflows the stack. The reason is apparently that the take function is not tail-recursive, and so it uses O(N) stack space.. What is the right way to do this? Sure, I could write my own tail-recursive generator function. But this seems to be an instance of a more general problem - how to avoid algorithms linear in stack space when dealing with large lists. Thanks a lot! Milos

7 12

"Wrong kind" when attempting to build a monad for a circular list of functions
by Aaron Altman 02 Mar '08

02 Mar '08

Hi everybody. I'm working towards a better understanding of Haskell monads the only way I know how: by working through an example. I am working on an AI agent that will perform a finite series of actions before starting the sequence over again. I figured a circular list of functions that shifts as you apply them would be the way to do it. Here is my test code: ----------------------------- import Control.Monad runActionAndIterate :: [a -> a] -> a -> (a, [a -> a]) runActionAndIterate (currentAction:actionList) actionInput = (currentAction actionInput, concat [actionList, [currentAction]]) shiftActionList :: [a -> a] -> [a -> a] shiftActionList (currentHead:rest) = concat [rest, [currentHead]] newtype CircularFuncList funcList arg = CircularFuncList (funcList -> arg -> (arg, funcList)) instance Monad (CircularFuncList funcList arg) where return a = CircularFuncList (\funcList a -> (a, funcList)) CircularFuncList currentFuncList currentArg >>= argTransform = let result = argTransform $ (head currentFuncList) currentArg newFuncList = map argTransform $ shiftActionList currentFuncList in CircularFuncList newFuncList result ----------------------------- I get an error that CircularFuncList funcList arg has kind * while Monad is looking for * -> *. This is a first attempt so it may be I'm a ways off from a monad that implements a circular list of functions. That is the goal though. What advice can you offer? Thanks, Aaron Altman

5 8

.cabal problem
by Galchin Vasili 02 Mar '08

02 Mar '08

Hello, I am trying to install a package on my Linux Ubuntu machine. It chokes build-depends: base, directory because directory dependency is unresolvable. Do I have to specify "extra-libs" so that correct library space is searched? Actually I tried this and it didn't help. ?? Regards, Vasya

2 2

Re: Generating a random list
by Milos Hasan 02 Mar '08

02 Mar '08

OK, you convinced me that sort is not the problem. After all, "last (f 1000000)" overflows too, and last is a very innocent function. I don't know how you found the size (or structure) of the thunks (I'm not aware of a ghci functionality that can tell me that), could you let me know? Anyway, the problem seems to be that the values pulled from the list are not final float values, but instead they're thunks that grow larger and larger as more floats are pulled from the list. That's why last and sort don't work, but print and foldl' do work. Also, an odd number of reverses helps since sort evaluates the elements from the end of the list first. So I forced those values, and it fixed the problem: -- this function returns n random floats (no thunks) f :: Int -> [Float] f n = take n $ randFloats $ mkStdGen 0 where randFloats g = x `seq` x : randFloats g' where (x, g') = random g main = print $ foldl1' (+) $ sort $ f 1000000 This works without overflow, and so does "last (f 1000000)". Would it make sense for System.Random to do this forcing by default, too? Thanks, Milos

1 0

runInteractiveCommand dying uncatchably?
by Evan Martin 02 Mar '08

02 Mar '08

If I run the following program, it never prints "done". If I uncomment the commented line, it does. import Prelude hiding (catch) import Control.Exception import System.Process import System.IO demo = do putStrLn "starting" (inp,out,err,pid) <- runInteractiveCommand "nonesuchcommand" putStrLn "writing to in on bad command" hPutStr inp "whatever" -- putStr "flushing" hFlush inp `catch` \e -> do print e; return () putStrLn "done" main = demo `catch` \e -> do print e; return () On my machine the output is: $ runhaskell test.hs starting writing to in on bad command $ It appears to exit at the hFlush call. (hClose has the same behavior.) I find this surprising -- I'd expect, even if I'm using an API incorrectly, to get an exception.

2 1

Announce: category-extras 0.1
by Dan Doel 01 Mar '08

01 Mar '08

Hello everyone, While fooling about with generalized tries a night or two ago, I found myself once again interacting with fixed points of shape functors and the like, and so decided it was time to finish cabalizing David Menendez' excellent category theory inspired modules.[1] So, it is my pleasure to announce version 0.1 of category-extras. This is an initial import of the code, with only what work it took to get things compiling properly. As such, some of the documentation is a bit scanty, and there is some overlap with other packages (notably, TypeCompose, off the top of my head), but I hope to rectify that later. Notable bits include: * Control.Comonad * Control.Comonad.Context -- the state-in-context monad * Control.Functor.Adjunction -- a class for adjoint functors, and their associated (co)monads * Control.Recursion -- Various generalized recursion operators (cata/zygo/histo/apomorphisms) -- A class for associating fixpoint data types to their shape functors Also included are some Data.* modules with some comonadic data types (infinite trees and streams, for instance), but they are in the as-yet-poorly-documented section of the package. Haddock 2.0 is required to build what documentation there is for Control.Functor.Transform, as it uses type operators. However, the rest should be compatible with earlier versions of haddock. Some modules are portable Haskell98, but many use various extensions (rank-2 types and functional dependencies being the most common). Links: * hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/category-extras-… * darcs: http://code.haskell.org/~dolio/category-extras/ If you identify any issues with the package, or simply have some wild category theoretic abstractions that you think should be made available to Haskell programmers at large, feel free let me know. -- Dan Doel [1] The original home of these modules is here: http://www.eyrie.org/~zednenem/2004/hsce/

1 0

Re: static constants -- ideas?
by Don Stewart 29 Feb '08

29 Feb '08

jay: > Don Stewart dons(a)galois.com: > > >jay: > >> Don Stewart dons(a)galois.com: > >> >jay: > >> >> Don Stewart dons(a)galois.com: > >> >> >jay: > >> >> >> I also have constants that are too large to compile. I am resigned to > >> >> >> loading them from data files--other solutions seem even worse. > >> >> ... > >> >> >> Data.Binary eases the irritation somewhat. > >> >> > > >> >> >Did you try bytestring literals (and maybe parsing them in-memory with > >> >> >Data.Binary)? > >> > >> I finally squeezed enough time to try it, and it didn't work for me. > > > >> > >> -- > >> ghc Overflow.hs > >> [1 of 1] Compiling Overflow ( Overflow.hs, Overflow.o ) > > > >Enable optimisations! Compile with ghc -O2. You need this to avoid > >having a very slow pack call at runtime. > > Yes, I tried basic variations like that. The result is the same with -O1 > or with -O2, and with Data.ByteString or Data.ByteString.Lazy . Ok, hmm, that really shouldn't be the case. Do you have the example available somewhere? It's just a 40M inline bytestring? -- Don

1 0

Re: static constants -- ideas?
by Don Stewart 29 Feb '08

29 Feb '08

jay: > Don Stewart dons(a)galois.com: > >jay: > >> Don Stewart dons(a)galois.com: > >> >jay: > >> >> I also have constants that are too large to compile. I am resigned to > >> >> loading them from data files--other solutions seem even worse. > >> ... > >> >> Data.Binary eases the irritation somewhat. > >> > > >> >Did you try bytestring literals (and maybe parsing them in-memory with > >> >Data.Binary)? > > I finally squeezed enough time to try it, and it didn't work for me. > > -- > ghc Overflow.hs > [1 of 1] Compiling Overflow ( Overflow.hs, Overflow.o ) Enable optimisations! Compile with ghc -O2. You need this to avoid having a very slow pack call at runtime. > Overflow.hs:8:10:stack overflow: use +RTS -K<size> to increase it > -- > > where Overflow.hs is in the vicinity of 40M and looks like > > -- > {-# LANGUAGE OverloadedStrings #-} > > module Overflow where > > import qualified Data.ByteString.Lazy as S > > bigData :: S.ByteString > bigData = "\0\0\0\0\0\5\67\195\0\0\0\0... > -- > > I didn't compress it, because Codec.Compression.GZip didn't compile for > me. It looked like a library change since 6.6 broke it. Probably you don't have the zlib.h header? Or make sure you have the latest version of zlib from hackage -- it does work. > Is there a handy string escaping function in the libraries somewhere? It > only took a minute to write one, and I spent longer than that looking, > so maybe it's the wrong question.... Surely it's in there somewhere, and > I'm just 2 dum 2 c. The show function?

1 0