- Haskell-Cafe - Haskell.org

Is there a best *nix or BSD distro for Haskell hacking?
by David Cabana 25 Apr '07

25 Apr '07

I have a spare Windows machine I want to put to better use. I want to turn it into a Haskell hacking box, and was wondering whether any particular *nix or BSD distribution is best (or worst) suited for this. Any thoughts? Thank you, David Cabana

13 14

About functional programing, type theory and a master thesis topic
by Glauber Cabral 25 Apr '07

25 Apr '07

Hi everybody =) First time I write to the list. My name is Glauber and I'm doing my master course at UNICAMP, Brazil, under supervisor of Prof. Dr. Arnaldo Vieira Moura. I'm interested in Haskell, type theory and algebraic specification (formal methods). I've been studying these subjects to my Computer-Science-Bachelor-degree-final work. It was an implementation of an homomorphism between a little constructive algebraic specification code (based mainly in Loeckx's Specification of Abstract Data Types) and a Haskell code. SableCC was used as tool to implement the interpreter because I've already used it before. One theme to work one should be implementing this in Haskell itself, but there is already HasCASL. I've already contacted the HasCASL professors and I'm reading more about the project. At the same time, I want to look for some theme under type theory, too. The main concern about HasCASL is that I want to get in deep touch with functional programming during my master thesis and I'm not sure (yet) if studying HasCASL would get me there. I've reading some papers about type theory and Haskell (mainly the ones suggested in the haskell.org site) and as I could see the topics are very interesting. I'm not sure, however, if there is something that can be done in a 2-year-master course. Mainly, they propose new extensions that have became new languages (Cayenne, Omega and Epigram). Other topic I'd like to get in touch is theorem proving. As I could see, Coq and Isabelle are the most used with Haskell. Indeed, HasCASL use Isabelle and this could be a nice thing to work on, as was suggested by HasCASL professors. As I know that lots of you here are researchers, I'd like to ask some opinions about what can be done as a master thesis having in mind that I want to continue in a PhD course after the master one. Sorry if the email is too large. And thank for the patience and for any opinion you can give me. Yours, Glauber.

2 4

Newbie seeking advice regarding data structure for a tricky algorithm
by Toby Hutton 24 Apr '07

24 Apr '07

Hi, I'm trying to implement a fast kd-tree in Haskell. http://en.wikipedia.org/wiki/Kd-tree It's a binary tree representing space partitions. One of the fastest ways to build kd-trees is outlined in this paper: http://www.cgg.cvut.cz/~havran/ARTICLES/ingo06rtKdtree.pdf (I'm trying to implement Algorithm 5 on page 5 and the steps outlined in section 4.3.1.) I'll try to outline a simplified analogous algorithm to demonstrate my problem. It's all about classifying which children should go in a left or right branch using heuristics. Say I want to put the words 'foo', 'bar' and 'baz' into a binary tree. The heuristic requires I split the words into letters and sort them: 'aabbfoorz'. The heuristic then may decide, based on the sorted letters, that 'bar' and 'foo' should go in the left child and 'baz' goes in the right. Typically we'd then simply recurse and for example, the left child's words would be re-sorted into 'abfoor' and the heuristic is reapplied. If we assume that sorting is relatively expensive, we can avoid the re-sort for the children by unmerging the parent's sorted list of letters. Two sublists of a sorted list should already be sorted. If we know which word each letter belongs to it would be more efficient to tag the letters with 'left' or 'right' as the words are classified. Then we can iterate down the sorted letter list and produce new sorted sublists rather simply. So it's not actually that complicated, and I can imagine exactly how it could be done in C but I really don't know how to approach this in Haskell. The problem I'm having is how to keep a map between the words and its letters (which in the real problem is a map between a list of vectors and 6 tuples containing Doubles and enumerations) while keeping in mind you can't just map any letter to a word, but specific letters. e.g., the 'b's in the example must remember specifically whether they belong to 'bar' or 'baz'. Thanks for any insights, Toby.

3 2

Haskell version of Norvig's Python Spelling Corrector
by Pete Kazmier 24 Apr '07

24 Apr '07

Recently I read an interesting article by Peter Norvig[1] on how to write a spelling corrector in 21-lines of Python. I wanted to try and implement it in Haskell. My implementation is terribly slow and I was hoping for some tips on how to improve it and make it idiomatic. I'd love to see other Haskell implementations as well if anyone has a few moments to spare. Admittedly, it took me several hours to get my version working, but I'm a Haskell newbie. Unfortunately, I think it runs as slow as it took me to write it! There is definitely something wrong with it, a memory leak, because I can't correct more than a few words without a great deal of memory being consumed. Thanks, Pete [1] http://norvig.com/spell-correct.html

10 21

Is Template Haskell a suitable macro language?
by Joel Reymont 24 Apr '07

24 Apr '07

I'm finding myself dealing with several large abstract syntax trees that are very similar in nature. The constructor names would be the same or one type may be a small extension of another. This is something that I wouldn't worry about with Lisp, for example, as I would create a bunch of macros for creating syntax trees and reuse them all over. I cannot do this in Haskell, though, as my "macros" are functions and so I must repeat them for every AST since they return different types. I'm wondering if Template Haskell is a suitable replacement for Lisp macros. What is the consensus? Thanks, Joel -- http://wagerlabs.com/

5 5

Re: haskell question
by oleg＠pobox.com 24 Apr '07

24 Apr '07

Greg Meredith wrote: > The file compiles with ghc as is. If you uncomment the last > section, however, you see that to close the loop on the constraints for the > agent syntax we hit a typing error. i <b><i>think</i></b> this is a hard > constraint in Haskell that prevents this level of generality in the > specification, but maybe you can see a way around it. I believe the Haskell typechecker is right > instance (Eq n, Eq p) => > CoreAgentSyntax (MinimalAgentSyntax n p) where > bind [] proc = Thunk (\() -> proc) > > data MinimalAgentSyntax n p = > Thunk (() -> p) > | Abstraction ([n] -> p) > | Concretion [n] p The bind method has the signature bind :: (CoreProcessSyntax p, CoreAgentSyntax x) => [n] -> (p a x) -> x That is: for any agent x and for _any_ process p (regardless of x), we should be able to perform the bind operation. The signature for bind proclaims total independence between 'p' and 'x'. However, when we define the instance > CoreAgentSyntax (MinimalAgentSyntax n p) where > bind [] proc = Thunk (\() -> proc) we see that process proc and the agent aren't totally independent: the result of bind has the type 'MinimalAgentSyntax n process' and thus is dependent on the 'process == p a x'. We have broken our previously made independence proclamation, and so the typechecker rightfully complaints. The following is one solution. It works sans the line marked TODO. I'm not sure that line is correct: -- -- TODO : lgm : need to substitute m for n in proc -- bind (name:names) proc = Abstraction (\m -> bind names proc) According to the type of Abstraction, 'bind names proc' should have the type 'p', that is, the same type as proc. It should be a process. OTH, bind returns an agent. Something is amiss here. {-# OPTIONS -fglasgow-exts #-} module Core where -- What's in a name? class Nominal n where nominate :: i -> n i newtype Name i = Nominate i deriving Eq instance Nominal Name where nominate i = Nominate i -- Where are we? class Locality a where locate :: (Eq s, Nominal n) => s -> (n i) -> a s (n i) name :: (Eq s, Nominal n) => a s (n i) -> (n i) data Location s n = Locate s n deriving Eq instance Locality Location where locate s n = Locate s n name (Locate s n) = n -- Constraints class CoreProcessSyntax p a x | p -> a x where zero :: p sequence :: a -> x -> p compose :: [p] -> p class CoreAgentSyntax x p n | x -> p n where bind :: [n] -> p -> x offer :: [n] -> p -> x -- Freedom (as in freely generated) data MinimalProcessSyntax l x = Null | Sequence l x | Composition [MinimalProcessSyntax l x] data MinimalAgentSyntax n p = Thunk (() -> p) | Abstraction ([n] -> p) | Concretion [n] p -- Constraining freedom instance CoreProcessSyntax (MinimalProcessSyntax l x) l x where zero = Null sequence l a = Sequence l a compose [] = zero compose ps = Composition ps instance CoreAgentSyntax (MinimalAgentSyntax n p) p n where bind [] proc = Thunk (\() -> proc) -- -- TODO : lgm : need to substitute m for n in proc -- bind (name:names) proc = Abstraction (\m -> bind names proc) -- here's the possible implementation. I don't know if it's right. -- But at least it types bind (name:names) proc = Abstraction (\m -> comp $ bind names proc) where comp (Thunk f) = f () -- comp (Concretion n p) = ... offer names proc = Concretion names proc

2 3

QuickCheck testing of AST transformers
by Joel Reymont 23 Apr '07

23 Apr '07

My previous post did not receive any replies so I thought I might try generalizing the problem a bit... Suppose I'm parsing a language into a syntax tree and then transforming that tree into another AST representing a "core language". The core language is a more general AST that should help with compiling to other languages. My problem is how to best structure my AST transformations to be able to test them with QuickCheck. I suspect that I'm not going about it in the most optimal way so I thought I should ask for suggestions. The transformation into the core AST applies operations to simplify, or desugar, the AST of the original language. Here's sample code in the source language which, incidentally, was recently highlighted at Lambda the Ultimate [1]. Array: MyArray[10](10 + 2); Value1 = MyArray[5][10]; This declares an array of 10 elements and initializes each element to 12. Value1 (a built-in variable) is then initialized to the value of element #5 as of 10 bars ago. A bar is, basically, a stock quote. The code is invoked on every bar and so "5 bars ago" can be treated as 5 invocations ago. The syntax tree of the above code is a 1-1 mapping. We declare an array of integers of 10 elements. Initialize it to the sum of two integers and then assign to Value1. [ ArrayDecs [ VarDecl (VarIdent "MyArray") TyInt [Int 10] (Op Plus (Int 10) (Int 2)) ] , Assign (VarIdent "Value1") [] (Var (VarIdent "MyArray") [Int 5] (BarsBack (Int 10))) ] The "desugared" version does away with the array declaration statement and declares MyArray to be a variable of array type. Arrays in the "core language" do not remember values from one invocation to another but there's a data series type, so we declare a series variable to hold the value of element #5. We must manually store the value of the array element in the data series and can then refer to the value of the series 10 data points ago. vars = [ ("MyArray", VarDecl (TyArray TyInt) [Int 10] (Just (Plus (Int 10) (Int 2)))) , ("series0", VarDecl (TySeries TyInt) [] Nothing) ] code = [ AddToSeries (VarIdent "series0") (Var (VarIdent "MyArray") [Int 5]) , Assign (Var (VarIdent "Value1") []) (Series (VarIdent "series0") (Int 10)) ] The next step would be to take the above "core syntax tree" and transform it yet again into a C# (or other target language) AST. It's assumed that all target languages have a data series type. The OCaml version of my code translated directly into the C# AST but I figured an intermediate syntax tree will help me translate into other languages such as Haskell, Erlang or OCaml. The part I can't figure out is how to come up with a set of invariants for my transformations. Should I, for example, state that every access to an array value in a previous invocation should introduce an extra variable to hold the series plus the appropriate assignment code? Should I write the translator as a series of small transformers in the ST monad that can be threaded and tested separately? Thanks in advance, Joel [1] http://lambda-the-ultimate.org/node/2201 -- http://wagerlabs.com/

3 2

Re: [Haskell-cafe] QuickCheck testing of AST transformers
by Thomas Schilling 23 Apr '07

23 Apr '07

Additionally, as a safety net, you might want to type-check the code that's being produced by your Arbitrary instances and state some invariants on your code. Also, you'll likely want to limit your number of evaluation steps if your language allows non-terminating programs. In any case, QuickCheck may not get you far enough to gain enough confidence, so proving properties by hand (after you made sure that QuickCheck doesn't find any counter-examples, of course) can give you interesting insights, since, this way, you have to take a look at all the possible cases yourself. /Thomas On 24 apr 2007, at 00.05, Lennart Augustsson wrote: > Without looking into your language and transformation in more > detail it's hard to come up with concrete suggestions. But here > are some anyway: > > Write an interpreter for each of your languages (original AST, > transformed AST) etc, and then use a quickcheck property stating > that well formed programs have the same denotation before and after > transformation, i.e., the two interpreters give the "same" value > (you might need some relaxed notion of same). > > You transformations are trying to get rid of some language > construct, I presume. So you can have some properties stating that > they will be gone in the transformed program.. > > -- Lennart > > > On Apr 23, 2007, at 22:46 , Joel Reymont wrote: > >> My previous post did not receive any replies so I thought I might >> try generalizing the problem a bit... >> >> Suppose I'm parsing a language into a syntax tree and then >> transforming that tree into another AST representing a "core >> language". The core language is a more general AST that should >> help with compiling to other languages. >> >> My problem is how to best structure my AST transformations to be >> able to test them with QuickCheck. I suspect that I'm not going >> about it in the most optimal way so I thought I should ask for >> suggestions. >> >> The transformation into the core AST applies operations to >> simplify, or desugar, the AST of the original language. Here's >> sample code in the source language which, incidentally, was >> recently highlighted at Lambda the Ultimate [1]. >> >> Array: MyArray[10](10 + 2); >> Value1 = MyArray[5][10]; >> >> This declares an array of 10 elements and initializes each element >> to 12. Value1 (a built-in variable) is then initialized to the >> value of element #5 as of 10 bars ago. A bar is, basically, a >> stock quote. The code is invoked on every bar and so "5 bars ago" >> can be treated as 5 invocations ago. >> >> The syntax tree of the above code is a 1-1 mapping. We declare an >> array of integers of 10 elements. Initialize it to the sum of two >> integers and then assign to Value1. >> >> [ ArrayDecs [ VarDecl (VarIdent "MyArray") TyInt [Int 10] >> (Op Plus (Int 10) (Int 2)) ] >> , Assign (VarIdent "Value1") [] (Var (VarIdent "MyArray") [Int 5] >> (BarsBack (Int 10))) ] >> >> The "desugared" version does away with the array declaration >> statement and declares MyArray to be a variable of array type. >> Arrays in the "core language" do not remember values from one >> invocation to another but there's a data series type, so we >> declare a series variable to hold the value of element #5. >> >> We must manually store the value of the array element in the data >> series and can then refer to the value of the series 10 data >> points ago. >> >> vars = [ ("MyArray", VarDecl (TyArray TyInt) [Int 10] >> (Just (Plus (Int 10) (Int 2)))) >> , ("series0", VarDecl (TySeries TyInt) [] Nothing) >> ] >> >> code = [ AddToSeries (VarIdent "series0") (Var (VarIdent >> "MyArray") [Int 5]) >> , Assign (Var (VarIdent "Value1") []) >> (Series (VarIdent "series0") (Int 10)) >> ] >> >> The next step would be to take the above "core syntax tree" and >> transform it yet again into a C# (or other target language) AST. >> It's assumed that all target languages have a data series type. >> >> The OCaml version of my code translated directly into the C# AST >> but I figured an intermediate syntax tree will help me translate >> into other languages such as Haskell, Erlang or OCaml. >> >> The part I can't figure out is how to come up with a set of >> invariants for my transformations. >> >> Should I, for example, state that every access to an array value >> in a previous invocation should introduce an extra variable to >> hold the series plus the appropriate assignment code? >> >> Should I write the translator as a series of small transformers in >> the ST monad that can be threaded and tested separately? >> >> Thanks in advance, Joel >> >> [1] http://lambda-the-ultimate.org/node/2201 >> >> -- >> http://wagerlabs.com/ >> >> >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

ANN: template 0.1 - Simple string substitution
by Johan Tibell 23 Apr '07

23 Apr '07

As an exercise I wrote a simple string substitution library that supports "$"-based substitution ala Perl or Python. Example usage: > import qualified Data.ByteString.Lazy.Char8 as B > import Text.Template > > context = Map.fromList . map packPair > where packPair (x, y) = (B.pack x, B.pack y) > > helloTemplate = B.pack "Hello, $name! Want some ${fruit}s?" > helloContext = context [("name", "Johan"), ("fruit", "banana")] > > main = B.putStrLn $ substitute helloTemplate helloContext Hopefully this is useful for someone who needs something more readable than Text.Printf's "%s"-based substitution or string concatenation for longer strings but less than a full blown templating system like the ones found in most web frameworks. Release: http://www.johantibell.com/template/template-0.1.tar.gz Source: darcs get http://darcs.johantibell.com/template Once we get ByteString literals most of the noise in the above example will disappear. In the mean time it's probably a good idea to write utility function like "context" above when you prefer a convenient String interface to a somewhat faster ByteString interface. It would be great if someone could do a code review and add it to Hackage if it looks OK. I'll really appreciate the feedback. Also, I'm not 100% sure how to make the haddock links work with Hackage so they link to the library docs. Is this something done at upload time? Here are some open issues: * I currently use my own ByteString parser. Data.Binary almost does what I need. Basically I need takeWhile and two chars of look-ahead. * I would like to only depend on base, currently I use State so I depend on mtl. Cheers, Johan

1 0

Announce: DisTract: Distributed Bug Tracker implemented in Haskell
by Matthew Sackman 23 Apr '07

23 Apr '07

DisTract is a Distributed Bug Tracker. We're all now familiar with working with distributed software control systems, such as Monotone, Git, Darcs, Mercurial and others, but bug trackers still seem to be fully stuck in the centralised model: Bugzilla and Trac both have single centralised servers. This is clearly wrong, as if you're able to work on the Train, off the network and still perform local commits of code then surely you should also be able to locally close bugs too. DisTract allows you to manage bugs in a distributed manner through your web-browser. Currently only Firefox is supported. The reason for this is that there is no local server used, and so the web-browser must directly (via Javascript) call programs on your local system. I only know how to do this in Firefox. The distribution is achieved by making use of a distributed software control system, Monotone. Thus Monotone is used to move files across the network, perform merging operations and track the development of every bug. Finally, the glue in the middle that generates the HTML summaries and modifies the bugs is written in Haskell. The first version, 0.1 has just been released. There are missing features currently, and I've only tested it on Linux. However, it should work on OS X and Windows if you can make it compile! It's only been tested with Monotone version 0.33. http://www.distract.wellquite.org/ Many thanks, Matthew

2 1