- Haskell - Haskell.org

RE: Questions about Trie
by Simon Peyton-Jones 18 May '01

18 May '01

Perhaps this monads discussion might move to haskell-cafe@haskell.org? It's a good discussion, but it's just what haskell-cafe is for. http://www.haskell.org/mailinglist.html Simon | -----Original Message----- | From: Arthur H. Gold [mailto:agold@bga.com] | Sent: 17 May 2001 22:21 | To: haskell(a)haskell.org | Cc: M. Faisal Fariduddin Attar Nasution | Subject: Re: Questions about Trie | | | > "M. Faisal Fariduddin Attar Nasution" wrote: | > | > Greeting, I'm a last year student in a computer science | field. I'm | > currently trying to code an implementation for a | compression using | > basic Lempel-zif technique. I use a Trie (retrieval) | as a data | > structure for the dynamic dictionary aplication. The | problem is Trie | > uses not just an ordinary binary tree, but it uses a | multiple-weighted | > tree, where one node has at most 256 children. Most | literatures about | > Haskell show only binary tree for the example in tree or | Abstract Data | > Structures subject. So, does anyone know how to | code the | > implementation for trie. Thanks for paying attention and | I'm really | > hoping for the answer immediately. | > | | IIRC, there's a trie implementation in Chris Okasaki's | "Purely Functional Data Structures" -- that might be a start | (there's also his "Edison" library, which contains many of | the components you'd need). | | HTH (and sorry if it doesn't) | --ag | | -- | Artie Gold, Austin, TX (finger the cs.utexas.edu account for | more info) mailto:agold@bga.com or mailto:agold@cs.utexas.edu | -- | I am looking for work. Contact me. | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

Questions about Trie
by M. Faisal Fariduddin Attar Nasution 17 May '01

17 May '01

Greeting, I'm a last year student in a computer science field. I'm currently trying to code an implementation for a compression using basic Lempel-zif technique. I use a Trie (retrieval) as a data structure for the dynamic dictionary aplication. The problem is Trie uses not just an ordinary binary tree, but it uses a multiple-weighted tree, where one node has at most 256 children. Most literatures about Haskell show only binary tree for the example in tree or Abstract Data Structures subject. So, does anyone know how to code the implementation for trie. Thanks for paying attention and I'm really hoping for the answer immediately. Aerith Gainsborough (Final Fantasy VII) "All I know is..." "The Cetra were born from the Planet, speak with the Planet, and unlock the Planet." "And....... then......" "The Cetra will return to the Promised Land. A land that promises supreme happiness." =================================== M. Faisal Fariduddin Attar Nasution ----------------------------------- farkinas(a)cbn.net.id

2 1

Wadler (was RE: Monads)
by Joe Bowers 17 May '01

17 May '01

There have been several references to "a paper by Wadler" in this thread- some folks (well, at least one folk :) on this list may not be familiar with the work surrounding Haskell yet, and (from this context) This paper seems like a pretty good place to start. Would anybody have a detailed citation for it, or (even better) is it up on the web? Joe

2 1

Re: Monads
by Ashley Yakeley 17 May '01

17 May '01

At 2001-05-17 02:03, Jerzy Karczmarczuk wrote: >Monads are *much* more universal than that. They are "convenient patterns" >to code the non-determinism (lazy list monads), to generalize the concept >of continuations, to add tracing, exceptions, and all stuff called >"computation" by the followers of Moggi. They are natural thus to construct >parsers. Imperative programming is just one facet of the true story. Perhaps, but mostly monads are used to model imperative actions. And their use in imperative programming is the obvious starting point to learning about them. -- Ashley Yakeley, Seattle WA

3 2

RE: Ix class
by Simon Peyton-Jones 17 May '01

17 May '01

I rather agree with Matt's message below. I'm desperately trying NOT to change the H98 libraries, but this is a very non-disruptive change, as he points out, and it does lift two apparently-unnecessary restrictions. a) Remove Ord from Ix's superclasses b) Add rangeSize to Ix's methods Does anyone have any thoughts about this. (We made a similar change to Random, adding a method.) Simon | -----Original Message----- | From: Matt Harden [mailto:matth@mindspring.com] | Sent: 16 May 2001 00:43 | To: Haskell list | Subject: Ix class | | | Hello, | | I am working on an Ix instance for one of my types and | finding it rather restrictive. For me it would be useful to | have rangeSize be defined in the Ix class (with a default | definition of course), so that it can be overridden. | | Also, does anybody know why Ix derives from Ord? It seems to | me this is an unnecessary limitation on the types that can be | instances of Ix. I cannot think of a reason why the | implementation of anything in the Ix or Array modules would | require that every Ix be an Ord (with a minor exception -- | see below). If an implementation is using a comparison on an | Ix type, chances are it should be using inRange or comparing | (index bnds x) with (index bnds y) instead. | | One change would have to be made in the Array module if Ord | is removed from Ix: | instance (Ix a, Eq b) => Eq (Array a b) where | a == a' = assocs a == assocs a' | instance (Ix a, Ord b) => Ord (Array a b) where | a <= a' = assocs a <= assocs a' | | would become: | instance (Ix a, Eq a, Eq b) => Eq (Array a b) where | a == a' = assocs a == assocs a' | instance (Ix a, Ord a, Ord b) => Ord (Array a b) where | a <= a' = assocs a <= assocs a' | | As I said, I think this is a very minor issue. | | I believe that making these changes in the standard would not | impact existing programs in any way. Could these changes be | considered as a possible "typo" to be fixed in the Library Report? | | | P.S. In case anybody's interested, here's why I want to override | rangeSize: | | > newtype Honeycomb = Hx (Int,Int) deriving (Eq,Show,Ord) | > | > indexError = error "Index out of range" | > | > instance Ix Honeycomb where | > range (Hx b1, Hx b2) = | > [Hx x | x <- range (b1,b2), isHexIx x] | > inRange (Hx b1, Hx b2) (Hx x) = | > inRange (b1,b2) x && isHexIx x | > index (Hx b1, Hx b2) (Hx x) = | > let i = index (b1,b2) x in | > if isHexIx x then i `div` 2 else indexError | > | > isHexIx :: (Int,Int) -> Bool | > isHexIx (x,y) = x `mod` 2 == y `mod` 2 | | This implements a honeycomb or hexagonal tiling for a maze | generating program. The honeycomb is superimposed on a grid | such that only every other square is "active", corresponding | to a particular hexagon in the honeycomb. It's similar to a | checkers game, where only the dark squares are used. | | I would like _any_ pair of Ints to be an acceptable boundary | for the honeycomb, not just the ones that represent valid | indexes. For example, (Hx (0,0), Hx (15,12)) should be a | valid set of bounds. The current definition of rangeSize | makes this impossible, which is why I would like to override | it. By the way, the Library Report does not explicitly say | that the bounds have to both be valid indexes, though it does | imply this with the sample definition of rangeSize. | | Thanks, | Matt Harden | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

Final CfP: BABEL Workshop on Multilanguage Infrastructure and Interoperability
by Nick Benton 17 May '01

17 May '01

BABEL'01 FINAL CALL FOR PAPERS First Workshop on Multi-Language Infrastructure and Interoperability http://research.microsoft.com/~nick/babel01.htm Satellite to PLI'01 Firenze, Italy, 8th September 2001 Submission Deadline: 1st June 2001 ** The Submission Site is now open ** http://cmt.research.microsoft.com/BABEL01/ AIMS AND SCOPE Recent years have seen a resurgence of interest in multi-language tools and intermediate languages, and in interoperability between programs and components written in different programming languages. Shared infrastructure such as code generators, analysis tools and garbage collectors can greatly ease the task of producing a high-quality implementation of a new programming language, whilst being able to interoperate easily with code written in existing languages is essential for such an implementation to be useful in practice. This workshop aims to bring together researchers and developers working on multi-language integration. Contributions are welcome on topics including, but not limited to: * Compilation of high level languages to common executable formats such as Sun's Java Virtual Machine, the DRA's ANDF or Microsoft's .NET Common Language Runtime. * Defining and using bindings for component middleware such as OMG's CORBA or Microsoft's COM. * Language constructs to support interoperability between different languages, particularly from different paradigms (e.g. OO/functional). * Multi-language backends for compilation and/or analysis (e.g. MLRISC, FLINT, C--, TAL, SUIF). * Type theoretic and semantic foundations for multi-language work. * Multi-language development environments and tools (e.g. debuggers, profilers). Submissions may address any programming paradigm. Experience papers which describe the use of multiple languages in application development are also welcome. Authors unsure of the appropriateness of a potential submission should email the PC chair (nick(a)microsoft.com) PROGRAMME COMMITTEE Nick Benton (chair) Microsoft Research Fergus Henderson University of Melbourne Andrew Kennedy (organiser) Microsoft Research Greg Morrisett Cornell University Martin Odersky Ecole Polytechnique Federale de Lausanne John Reppy Bell Labs Andrew Tolmach Portland State University David Wakeling University of Exeter INVITED SPEAKERS Zhong Shao Yale University IMPORTANT DATES Deadline for submission 1st June 2001 Notification of acceptance 9th July 2001 Final version due 10th August 2001 SUBMISSION DETAILS Papers should be at most 14 pages and should be submitted in Ghostscript-compatible PostScript or PDF format and be printable on both US letter and A4 paper. Authors are strongly encouraged to use ENTCS style files (see http://math.tulane.edu/~entcs/) <http://math.tulane.edu/~entcs/) > Papers should be submitted electronically via the submission site at http://cmt.research.microsoft.com/BABEL01/ Submissions should not overlap significantly with work which has already been published or submitted to any other conference or journal. An informal proceedings will be published as a technical report and distributed at the workshop. It is intended that a final proceedings will be published in a volume of ENTCS.

1 0

RE: Monads
by Peter Douglass 17 May '01

17 May '01

I should probably mention that one doesn't need to know that a list is a monad in order to use a list. However, understanding that a list obeys the monad laws is a useful way to learn about monads. --PeterD > -----Original Message----- > From: Peter Douglass > Sent: Thursday, May 17, 2001 9:26 AM > To: 'bedloose(a)hotmail.com'; haskell(a)haskell.org > Subject: RE: Monads > > > Monads are used not only for programming IO, state, > exceptions etc, but also > are the foundation of lists. It is hard to imagine > functional programming > without this basic datatype. Sets, Bags, trees etc are also > monads. Phil > Wadler wrote a very useful paper Comprehending Monads which I > notice is not > found on the Haskell/bookshelf web page. It can be found at > > http://www.cs.bell-labs.com/who/wadler/topics/monads.html > > I recommend this page for anyone interested in monads. > --PeterD > > > > -----Original Message----- > > From: Mads Skagen [mailto:bedloose@yahoo.dk] > > Sent: Thursday, May 17, 2001 4:25 AM > > To: haskell(a)haskell.org > > Subject: Monads > > > Hi > > > I'v currently working on a school-project where I have > > to describe the Haskell programming language. > > > I've been looking through Monads and especially the IO > > monad, the Maybe monad and the list monad > > > > My question is why are monads necessary in the > > language ? > > > Is it not possible to construct the features provided > > by Monads using basic functional constructs ? > > > What do I gain using Monads ? > > > Thank you very much. > > > Regards Skagen > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

1 0

RE: Monads
by Peter Douglass 17 May '01

17 May '01

Monads are used not only for programming IO, state, exceptions etc, but also are the foundation of lists. It is hard to imagine functional programming without this basic datatype. Sets, Bags, trees etc are also monads. Phil Wadler wrote a very useful paper Comprehending Monads which I notice is not found on the Haskell/bookshelf web page. It can be found at http://www.cs.bell-labs.com/who/wadler/topics/monads.html I recommend this page for anyone interested in monads. --PeterD > -----Original Message----- > From: Mads Skagen [mailto:bedloose@yahoo.dk] > Sent: Thursday, May 17, 2001 4:25 AM > To: haskell(a)haskell.org > Subject: Monads > Hi > I'v currently working on a school-project where I have > to describe the Haskell programming language. > I've been looking through Monads and especially the IO > monad, the Maybe monad and the list monad > > My question is why are monads necessary in the > language ? > Is it not possible to construct the features provided > by Monads using basic functional constructs ? > What do I gain using Monads ? > Thank you very much. > Regards Skagen

1 0

HUGS error: Unresolved overloading
by David Scarlett 17 May '01

17 May '01

Can anyone shed some light on the following error? Thanks in advance. isSorted :: Ord a => [a] -> Bool isSorted [] = True isSorted [x] = True isSorted (x1:x2:xs) | x1 <= x2 = isSorted (x2:xs) | otherwise = False -------- Hugs session for: /usr/local/share/hugs/lib/Prelude.hs haskell/sort.hs Main> isSorted [1] True Main> isSorted [1,2] True Main> isSorted [2,1] False Main> isSorted [] ERROR: Unresolved overloading *** Type : Ord a => Bool *** Expression : isSorted [] --------

2 1

Re: Monads
by Ashley Yakeley 17 May '01

17 May '01

At 2001-05-17 01:25, Mads Skagen wrote: >My question is why are monads necessary in the >language ? > >Is it not possible to construct the features provided >by Monads using basic functional constructs ? Monads themselves are made purely out of basic functional constructs. >What do I gain using Monads ? They happen to be a very convenient pattern. Mostly they're used to model imperative actions: while a purely functional language cannot actually execute actions as part of its evaluation, it can compose them, along the lines of "AB is the action of doing A, and then doing B with its result". Monads happen to be a useful pattern for such things. -- Ashley Yakeley, Seattle WA

2 1