February 2008 - Haskell-Cafe

Trouble finding exception source
by Denis Bueno 27 Feb '08

27 Feb '08

Hi all, I've got some code crashing with "Prelude.foldr1: empty list". In GHCi, the code uses too much memory (I kill it after it consumes 1GB) to be able to use :trace and :history, but I just found out about the -xc RTS option. I tried that, and I get the following: <GHC.List.CAF>dsat: Prelude.foldr1: empty list Now, manually going through GHC.List (http://haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-List.html) I only found one CAF, namely prel_list_str, at the bottom of the file. However, it is late and I quite possibly missed something. This CAF, of course, doesn't seem a likely culprit. I also stumbled on some discussion of the explicit call stack (http://hackage.haskell.org/trac/ghc/wiki/ExplicitCallStack/StackTraceExperi…) which exemplifies the behavior I've found, but doesn't seem to suggest a way to fix it. I'm developing on GHC 6.8.2. I've attached my code, the output of a cabal sdist, which requires parse-dimacs [0] and bitset [1] (both cabalised) to build. If you build the executable (with profiling), you should see my behavior by running: ./dist/build/dsat/dsat -verify +RTS -xc I know that the problem is somewhere in the "Backtracking" section, in the backJump function. But I don't know where. Any help is appreciated. -- Denis [0] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/parse-dimacs-1.0… [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bitset-0.5

3 4

Stack overflow
by Grzegorz Chrupala 27 Feb '08

27 Feb '08

Hi all, I have a very simple program which reads a Data.Map from a file using Data.Binary and Data.ByteString.Lazy, which gives stack overflow with files over a certain size. Any ideas of what might be causing it? You can try it with the small file (11M) at: http://computing.dcu.ie/~gchrupala/map.bin import System import Data.Map import qualified Data.ByteString.Lazy as BS import Data.Binary main = do [path] <- getArgs m <- fmap decode (BS.readFile path)::IO (Map (Int,Maybe String) Int) putStrLn . show . findMax $ m -- Grzegorz -- View this message in context: http://www.nabble.com/Stack-overflow-tp15479718p15479718.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

5 13

RFC: SAT solver using Cont/callCC for backtracking search
by Denis Bueno 26 Feb '08

26 Feb '08

Hi all, I've recently done a small Haskell port of some OCaml code from a paper entitled "SAT-MICRO: petit mais costaud!" It's a tiny (one emacs buffer for the algorithm, ~160 lines overall) DPLL SAT solver with non-chronological backtracking, implemented using the Cont monad and callCC. If anyone has time and interest, I'm requesting comments on how the code could be improved in any way: style, efficiency, etc. The code in the paper is OCaml which uses exceptions as the main control-flow mechanism for backtracking. If you can read French, you may be interested in the paper, which is available here: http://hal.inria.fr/inria-00202831/en/ Of course, you will likely understand the OCaml code even if you don't understand French. Thanks in advance to anyone who comments. -- Denis

2 3

Re: [Haskell-cafe] Problem with Python AST
by Roel van Dijk 26 Feb '08

26 Feb '08

On Fri, Feb 22, 2008 at 2:42 PM, Daniel Gorín <dgorin(a)dc.uba.ar> wrote: > > On Feb 21, 2008, at 7:55 PM, Roel van Dijk wrote: > > > Your solutions allows a bit more but fails with the equivalent of > > > > def foo(): > > for i in range(10): > > if i == 6: > > return None > > > > The loop context 'overwrites' the function context which makes the > > return statement illegal. I think I need a type level list. > > i see. how about this? > > if_ = If [(IntLit 6, Suite [] [Break])] (Just $ Suite [] [Return]) > while_ = While (IntLit 6) (Suite [] [if_]) Nothing > while2_ = While (IntLit 6) (Suite [] [Return]) Nothing > foo = FunDecl $ Suite [] [while_, while2_] > > p = Program [foo] > > > newtype Ident = Id String > > data BinOp = Add > | Sub > > data Exp = IntLit Integer > | BinOpExp BinOp Exp Exp > > data Ctx reqloop reqfun > data True > data False > > data Statement ctx where > If :: [(Exp, Suite (Ctx reqloop reqfun))] > -> Maybe (Else (Ctx reqloop reqfun)) > -> Statement (Ctx reqloop reqfun) > While :: Exp > -> (Suite (Ctx True reqfun)) > -> Maybe (Else (Ctx True reqfun)) > -> Statement (Ctx reqloop reqfun) > Pass :: Statement (Ctx reqloop reqfun) > Break :: Statement (Ctx True reqfun) > Return :: Statement (Ctx reqloop True) > FunDecl :: Suite (Ctx False reqfun) -> Statement (Ctx False False) > > newtype Global = Global [Ident] > > data Suite ctx = Suite [Global] [Statement ctx] > > type Else ctx = Suite ctx > > newtype Program = Program [Statement (Ctx False False)] Ah, you set a specific context when needed. Very nice. Although I had to remove the Ctx type. Otherwise I need pattern matching at the type level to bind the reqLoop and reqFun type variables (is such a thing even possible?): data Statement (Ctx reqLoop reqFun) where .... Now I simple pass 2 type variables to my statements: data Statement reqLoop reqFun where .... I now have a complete Python AST and pretty printer. Onwards towards a parser! Thanks again, Roel

2 1

Re: [Haskell] Re: [Haskell-cafe] GSoC 2008
by Duncan Coutts 26 Feb '08

26 Feb '08

On Tue, 2008-02-26 at 23:39 +0100, Lemmih wrote: > On Tue, Feb 26, 2008 at 8:43 PM, Johan Tibell <johan.tibell(a)gmail.com> wrote: > > On Mon, Feb 25, 2008 at 3:28 PM, Malcolm Wallace > > <Malcolm.Wallace(a)cs.york.ac.uk> wrote: > > > Google has today announced that they will be running their Summer of > > > Code programme again this year. > > > http://code.google.com/soc/2008/ > > > > > > haskell.org has had many student projects funded by this programme, in > > > 2006 and 2007. Would you like to participate? Either as a student or > > > a mentor? > > > > I'd like to see a Unicode equivalent of ByteString and I'm willing to > > mentor someone who's willing to implement it. > > Doesn't compact-string support unicode? Yes but not everyone agrees that it had the right interface. There was an interesting discussion on #haskell a month or so ago on the question of whether a string type should be parametrised by an encoding type or not. John and I were amongst those of the view that it should not. I also noted to John earlier that a MSc student I'm supervising is expected to complete this project before the GSoC coding phase kicks off so it's probably not the best choice for a GSoC project. Duncan

1 0

fast graph algorithms without object identities
by Henning Thielemann 26 Feb '08

26 Feb '08

It seems that algorithms on graphs can be implemented particularly efficient in low-level languages with pointers and in-place updates. E.g. topological sort needs only linear time, provided that dereferencing pointers requires constant time. I could simulate pointer dereferencings and pointer updates by Map yielding linear logarithmic time for topological sort. I wonder if it is possible to write a linear time topological sort using lazy evaluation, since the runtime system of Haskell implementations is a graph processor based on pointers.

4 5

GSoC 2008
by Malcolm Wallace 26 Feb '08

26 Feb '08

Google has today announced that they will be running their Summer of Code programme again this year. http://code.google.com/soc/2008/ haskell.org has had many student projects funded by this programme, in 2006 and 2007. Would you like to participate? Either as a student or a mentor? Come and meet up in #haskell-soc on freenode.net. We need to discuss and craft our organisation's application to Google, by March 12th. We need to have ideas for projects before students apply to Google on March 24th. We need volunteers for adminstration. This is community stuff! All sorts of people can play a part. Regards, Malcolm

2 1

Trees building
by Krzysztof Skrzętnicki 26 Feb '08

26 Feb '08

Hi everyone I'm trying to write a piece of Haskell code, but for some reason I can't make it working. I'm asking for your help in finding a bug in this code: > import Data.Tree > import Data.List > expandTree :: Int -> [(Int,Int)] -> ((Tree Int),[(Int,Int)]) > expandTree rootLabel [] = ((Node rootLabel []),[]) -- probably obsolete line > expandTree rootLabel nodePairs = ((Node rootLabel forest),unused) > where > (marked,unmarked) = partition (\ (x,y) -> (x==rootLabel) || (y==rootLabel)) nodePairs > (forest,unused) = foldl > (\ (forestAcc, unusedPairs) node -> let (a,b) = expandTree node unused in ((a:forestAcc),b) ) > ([],unmarked) > (map (\(o,p)-> if o == rootLabel then p else o ) marked) It is supposed to create tree with root labeled with rootLabel, while nodePairs is a description of a tree. If a list is not exhausted, the remaining should be returned. It should work so that: expandTree 1 [(1,2)] == ((Node 1 [(Node 2 [])]),[]) expandTree 1 [(2,3)] == ((Node 1 []),[(2,3)]) expandTree 1 [(1,2),(3,4)] == ((Node 1 [(Node 2 [])]),[(3,4)]) However, the code loops. Any clues? Thanks in advance. Regards Christopher Skrzętnicki

2 1

derivation of mapP, a parallel, lazy map
by Dan Zwell 26 Feb '08

26 Feb '08

Hello, everyone. I have just written a tutorial (sort of) on Haskell concurrency, specifically on the derivation of a function mapP, a parallel version of map. I wrote this because I am fairly new to Haskell, and I didn't realize how easy concurrent code is until I wrote this, and because I could not find a tutorial describing a parallel implementation of map. If anybody is curious to see this, the page is http://zwell.net/content/haskell.html#mapP . I would appreciate any criticism, too. I hope somebody finds this helpful. Dan Zwell

5 8

noob question
by Ben 26 Feb '08

26 Feb '08

I'm just starting to learn Haskell, and I'm having some confusion (I think) with how the type inference is working. Can someone explain why, in ghc 6.8.2 this works: *Main> (1/3)^3 3.7037037037037035e-2 But this doesn't *Main> (\k -> (1/k) ^ k) 3 <interactive>:1:8: Ambiguous type variable `t' in the constraints: `Fractional t' arising from a use of `/' at <interactive>:1:8-10 `Integral t' arising from a use of `^' at <interactive>:1:7-15 Probable fix: add a type signature that fixes these type variable(s) TIA, Ben

6 8