- Haskell-Cafe - Haskell.org

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

27 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 27 Feb '08

27 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 27 Feb '08

27 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

"Computational Category Theory" in Haskell
by Dan Weston 26 Feb '08

26 Feb '08

Has anyone already ported to Haskell the ML code in Rydeheard and Burstall, "Computational Category Theory"? Dan

3 2

Graphical graph reduction
by dainichi＠gmail.com 26 Feb '08

26 Feb '08

Hi Haskell-Cafe, I'm relatively new to Haskell, but have a background with SML. One of the things that amaze me about Haskell is lazy graph reduction, e.g. how the graph unfolds during the evaluation of, say, let fibs = 1 : 1 : zipWith (+) fibs (tail fibs) in take 10 fibs Lazy lists can be simulated in SML too, but unless I do something clever with references, I end up taking exponential time to compute the n'th Fibonacci number. Now to the point: Wouldn't it be great if I had a visual tool that visually showed me the graph while the above evaluation unfolded? I could use it to show some of my co-workers to whom laziness is a mystery, what it's all about. Does anybody know if such a tool exists? I'd be grateful for pointers if it does. I very much doubt that I'm the first person who has thoughts like this, but then again, who knows. People who really know Haskell might think this is too trivial a task to really be worth spending time on. If nothing similar exists, I was thinking about creating such a tool (i.e. an interpreter with additional graph-displaying features) for a very, very small subset/dialect of Haskell. I would probably be lazy (no pun intended) and start right away with abstract syntax trees to avoid lexing and parsing and such. My language of implementation would be SML, using references as the edges of the graph. Any ideas/comments would be welcome. Kai

11 12