- Wikibook - Haskell.org

(fwd) Re: question from Yet Another Haskell Tutorial
by Benjamin L.Russell 31 Mar '09

31 Mar '09

A new page has been added to the Haskell Wikibook, as an Errata page for YAHT. See the following message forwarded from Haskell-Beginners: On Mon, 30 Mar 2009 20:33:29 +0900, in gmane.comp.lang.haskell.beginners Benjamin L.Russell <DekuDekuplex(a)Yahoo.com> wrote: >On Sun, 29 Mar 2009 14:45:22 +0200, Daniel Fischer ><daniel.is.fischer(a)web.de> wrote: > >>Simple mistake. YAHT was never systematically proofread to catch all >>such mistakes, so there are several still in. Nevertheless, it is an >>excellent tutorial. > >Thank you both, Michael and Daniel. I have compiled the information >in this thread into a new page, "Errata," in the YAHT Wikibook, >covering discrepancies between the original PDF and corrected HTML >versions of YAHT: > >Haskell/YAHT/Errata - Wikibooks, collection of open-content textbooks >http://en.wikibooks.org/wiki/Haskell/YAHT/Errata > >Please feel free to add to it or to correct it as would benefit >students of Haskell. Enjoy! -- Benjamin L. Russell -- Benjamin L. Russell / DekuDekuplex at Yahoo dot com http://dekudekuplex.wordpress.com/ Translator/Interpreter / Mobile: +011 81 80-3603-6725 "Furuike ya, kawazu tobikomu mizu no oto." -- Matsuo Basho^

2 1

New template for referencing standard library haddocks
by apfelmus 05 Aug '07

05 Aug '07

Hello wikibookians, There's a new template for referencing standard library haddocks. http://en.wikibooks.org/wiki/Template:Haskell_lib - What does this template do? - This template generates links to the documentation of GHC's standard library modules. For example, if you talk about Control.Monad and want the text to be a proper link to the latest GHC Haddocks, this template is for you. Arguably, automatic syntax coloring and hyperlinking of Haskell source code should obsolete this template. - Usage - {{Haskell lib|Control|Monad}} => Control.Monad from the base-package. {{Haskell lib|package=mtl|Control|Monad|State}} => Control.Monad.State from the mtl-package. Currently, the module name may be only 5 levels deep, but that's easy to change. Regards, apfelmus

1 0

Re: Haskell wikibook - chapter "Theseus and the Zipper"
by apfelmus 08 Jul '07

08 Jul '07

Dear Mr. Huet, > Very nice indeed. > > The analogy with Ariadne's thread is a natural one. I use myself the > analogy with mountaineering, you are hanging from the top of the > datastructure using the zipper as a return rope. > > Compliments on a nice site on functional programming. Keep up the good > work. Thank you very much for the encouragement, we are delighted that you appreciate our efforts :) The aim of the Haskell wikibook is to write a free and gentle textbook on Haskell and associated techniques for functional programming. Of course, to keep up the good work, we are always looking for contributors. In fact, the book lives through contributions from its readers: it is built with a wiki, utilizing the same platform as Wikipedia and hence sharing the same principle that anyone can edit. > After I learned of Conor Mc Bride's work, I wrote some more about > zippers for a de Bruijn's Festschrift, see item 79 in my bibliography > [http://yquem.inria.fr/~huet/bib.html] > > My main application of zippers so far has been for the design of the > Zen toolkit for computational linguistics, see items 78,82,84,85 and > site http://sanskrit.inria.fr/huet/ZEN/index.html. This toolkit was > reused in Haskell by the Grammatical Framework linguistic platform of > Aarne Ranta. Very interesting. Pondering the sharing functor, I think there is a way to make practical the Gödel-numbering you mentioned on page 10 of item 78. The starting point is that I personally have a slight distaste for hash tables since they are tied to machine numbers and arrays, concepts alien to algebraic data types and purely functional programming. I prefer tries, i.e. finite representations of functions key -> value From the point of view of computational complexity, they are optimal: lookup and insertion all take O(|size of key in bits|) time. Tries can be obtained systematically from the structure of the key type by the isomorphisms (key1 + key2) -> value ≅ (key1 -> value) × (key2 -> value) trie for a sum type ⇒ pair two tries for the components (key1 × key2) -> value ≅ (key1 -> (key2 -> value)) trie for a product type ⇒ nest the tries for the components See also Ralf Hinze. Generalizing generalized tries. Journal of Functional Programming, 10(4):327-351, July 2000 http://www.informatik.uni-bonn.de/~ralf/publications/GGTries.ps.gz From now on, the function arrow -> shall denote a finite map from keys to values, so that every -> type is represented by an algebraic data type. In particular, it is possible to construct a generalized trie with a key type ([Char] -> Bool) representing a set of words (Haskell-like syntax, I don't know ML). Thus, both your hash table with subtries of the dictionary as keys and a generalized trie with subtries as keys represent a map ([Char] -> Bool) -> value ≅ (µX. Bool × (Char -> X)) -> value Of course, replacing the hash table with the generalized trie corresponds to the one-to-one Gödel numbering of the keys as you mentioned on page 10 of item 78. In a sense, the subtries as keys are (a representation of) their own Gödel numbers. But now, Gödel-number equality is the structural equality of the tries which defeats the hole purpose of avoiding repeated traversal of the subtries of the dictionary. Put differently, even a numeric Gödel-numbering cannot decrease the size of the tries or it would not be able to represent every possible trie. The solution is to restrict the Gödel-numbering to the set of tries we are interested in, namely to all the subtries of the dictionary. The intention is that the Gödel numbers sort of simply enumerate the subtries from 1 to n. In other words, the finite map storing the subtries becomes a structure storing "local Gödel numbers" type Subtrie = µX. Bool × (Char -> X) type Gödel = Int type GödelStore ≅ Subtrie -> Gödel The key is that the Gödel numbers can now be used to break the recursion, yielding type GödelStore = (Bool × (Char -> Gödel)) -> Gödel Put differently, a subtrie is represented by its topmost branches with the children being Gödel numbers instead of hole tries. By traversing the dictionary bottom-up, we have the Gödel numbers of subtries available before assigning a Gödel number to the parent. The parent gets a fresh Gödel number when its not in the GödelStore, otherwise we use the Gödel number from the store and thus share this subtrie. In fact, your current hashing scheme proceeds essentially the same way: a hash number is calculated from the already calculated hash numbers of the children. Maybe your current hash-table implementation could already benefit from Gödel numbers. The insight is to separate Gödel numbers representing hole subtries and hash numbers which may be used to implement the "shallow" GödelStore as a hash table. The benefit is that in case of a collision, the expensive test for structural equality is replaced with a cheap check for Gödel number equality. All the best, apfelmus > Le 30 juin 07 à 10:40, apfelmus(a)quantentunnel.de a écrit : >> Dear Mr. Huet, >> >> Fascinated by the zipper since reading your publication, the authors >> of the Haskell wikibook have written a special introduction to this >> data structure: >> >> "Theseus and the Zipper". >> http://en.wikibooks.org/wiki/Haskell/Zippers >> >> starring Theseus and Ariadne. We hope you will enjoy it :) >> >> All the best, >> apfelmus

1 0

Greetings!
by Brent Yorgey 05 Jul '07

05 Jul '07

Hi all, Allow me to introduce myself -- I'm an avid Haskell hobbyist (though hoping to be a PhD student soon) looking for ways to contribute to the Haskell community, and have found the wikibook to be one place where I can combine my love of Haskell with my teaching and writing skills to make a positive contribution. I've already overhauled the Recursion module and also made some minor edits to the List processing module; please feel free to take a look and let me know if anything I've done doesn't fit with the overall project goals/style etc. (or just edit it yourself =). For now I plan to continue going through the Elementary Haskell track doing cleanup/editing/making additions and so on. We'll see how far I get... Anyway, just thought I would say "hi"! I'm usually hanging out in #haskell and #haskell-blah (as byorgey) when online, and I plan to hang out in #haskell-books now too, if you should care to chat for any reason. cheers, -Brent

1 0

Fwd: Haskell wikibook - chapter "Theseus and the Zipper"
by apfelmus 01 Jul '07

01 Jul '07

> Von: Gérard Huet <Gerard.Huet(a)inria.fr> > Datum: 30. Juni 2007 14:09:23 MESZ > An: apfelmus(a)quantentunnel.de > Cc: Gérard Huet <Gerard.Huet(a)inria.fr> > Betreff: Re: Haskell wikibook - chapter "Theseus and the Zipper" > > Very nice indeed. > The analogy with Ariadne's thread is a natural one. I use myself the > analogy with mountaineering, you are hanging from > the top of the datastructure using the zipper as a return rope. > > After I learned of Conor Mc Bride's work, I wrote some more about > zippers for a de Bruijn's Festschrift, see > item 79 in my bibliography [http://yquem.inria.fr/~huet/bib.html] > > My main application of zippers so far has been for the design of the > Zen toolkit for computational linguistics, see > items 78,82,84,85 and site > http://sanskrit.inria.fr/huet/ZEN/index.html. > This toolkit was reused in Haskell by the Grammatical Framework > linguistic platform of Aarne Ranta. > > Compliments on a nice site on functional programming. Keep up the good > work. > Gerard > > Le 30 juin 07 à 10:40, apfelmus(a)quantentunnel.de a écrit : > >> Dear Mr. Huet, >> >> Fascinated by the zipper since reading your publication, the authors >> of the Haskell wikibook have written a special introduction to this >> data structure: >> >> "Theseus and the Zipper". >> http://en.wikibooks.org/wiki/Haskell/Zippers >> >> starring Theseus and Ariadne. We hope you will enjoy it :) >> >> All the best, >> apfelmus >> >

1 0

Haskell wikibook - chapter "Theseus and the Zipper"
by apfelmus＠quantentunnel.de 30 Jun '07

30 Jun '07

Dear Mr. Huet, Fascinated by the zipper since reading your publication, the authors of the Haskell wikibook have written a special introduction to this data structure: "Theseus and the Zipper". http://en.wikibooks.org/wiki/Haskell/Zippers starring Theseus and Ariadne. We hope you will enjoy it :) All the best, apfelmus

1 0

Re: [Haskell wikibook] Using XHTML Elements in the Wikibook
by PR Stanley 19 May '07

19 May '07

>>I am not suggesting there's any problem. all I'm saying is that a >>more effective use of XHTML elements would increase >>accessibility. for example, more headings, lists. Perhaps we could >>even use CSS if the wiki framework allows it. The wikibook is, and I repeat, fully navigable for the most part but that shouldn't preclude us from striving for perfection. Paul >>Fortunately, the Haskell Wikibook is for the most >>part fully navigable; however, the inclusion of >>XHTML elements would increase accessibility hugely. > >But the Wiki markup is transformed to XHTML anyway; if you download >e.g. http://en.wikibooks.org/wiki/Haskell, that's pure XHTML, not Wiki >markup. What's the problem? > >-- >-David House, dmhouse(a)gmail.com

2 1

Using XHTML Elements in the Wikibook
by PR Stanley 19 May '07

19 May '07

Hello again One of you chaps once told me that XHTML elements had no place in the Wikibook: the rationale being that everyone, regardless of his knowledge of mark-up languages, should be encouraged to contribute to the wiki text. I'm wondering if a small amount of HTML tagging may not be such a bad idea considering the accessibility benefits. What does the list think? Cheers, Paul

4 4

Where is the Wikibook?
by PR Stanley 13 May '07

13 May '07

Hi folks, I've not looked at the Wikibook for quite sometime. Now I'm having difficulty locating the wiki pages. Have they been moved? If the wikibook is still in existence, could someone send me its URL please? Thanks, Paul

2 1

hcar report
by Eric Y. Kow 23 Apr '07

23 Apr '07

Dear Haskell wikibookians, I am having a hard time writing up our HCAR report, lately. Anybody want to take a stab at it? Here is my very clumsy attempt. -- Eric Kow http://www.loria.fr/~kow PGP Key ID: 08AC04F9 Merci de corriger mon français.

3 6