Hi, all,
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.). It is intended to show how people with disabilities similar to Stephen Hawking's (i.e., good cognitive hability, but very few movements) can write text. http://hackage.haskell.org/package/bitspeak http://bitbucket.org/mauricio/bitspeak/wiki/Home Best, Maurício _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 21.06.2010 23:50, Maurício CA wrote:
> Hi, all, > > bitspeak is a small proof of concept application that allows > writing text using only two commands (yes/no, 1/2, top/down etc.). Looks cool! Did you forget any dependencies tho? I get the following error: 0:16 nils` cabal update Downloading the latest package list from hackage.haskell.org 0:17 nils` cabal install bitspeak Resolving dependencies... Configuring bitspeak-0.0.1... Preprocessing executables for bitspeak-0.0.1... Building bitspeak-0.0.1... src/Main.hs:7:7: Could not find module `Corpora': Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: bitspeak-0.0.1 failed during the building phase. The exception was: ExitFailure 1 Thx, Nils _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Maurício CA
2010/6/21 Maurício CA <[hidden email]>:
> Hi, all, > > bitspeak is a small proof of concept application that allows > writing text using only two commands (yes/no, 1/2, top/down etc.). > It is intended to show how people with disabilities similar to > Stephen Hawking's (i.e., good cognitive hability, but very few > movements) can write text. Neat! Have you looked at Dasher? http://www.inference.phy.cam.ac.uk/dasher/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Maurício CA
On Mon, Jun 21, 2010 at 06:50:41PM -0300, Maurício CA wrote:
> bitspeak is a small proof of concept application that allows > writing text using only two commands (yes/no, 1/2, top/down etc.). > It is intended to show how people with disabilities similar to > Stephen Hawking's (i.e., good cognitive hability, but very few > movements) can write text. There is a parallel between data compression algorithms and this sort of task, expressing a sentence in the minimal number of bits via compression also minimized the number of yes/no questions that need to be asked. In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Nils Schweinsberg
>> bitspeak is a small proof of concept application that allows
>> writing text using only two commands (yes/no, 1/2, top/down etc.). > > Looks cool! Did you forget any dependencies tho? I get the following error: > Oops... Three modules ended up missing in .cabal file. Just uploaded 0.0.2 to hackage, it should work. Thanks! Maurício _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by John Meacham
>> bitspeak is a small proof of concept application that allows
>> writing text using only two commands (yes/no, 1/2, top/down etc.). > > There is a parallel between data compression algorithms and this sort of > task, expressing a sentence in the minimal number of bits via > compression also minimized the number of yes/no questions that need to > be asked. > > In particular, a Huffman coding: Sure, Huffman was actually my first tought. But I couldn't think of a pratical display for the result of Huffman encoding that could be easily followed by a human looking at the screen. Since it's an optimal code, letters would not be grouped in alphabetical order. Thinking again, this could be easily accomplished... I could just list the alphabet and the next bit to be choosed below each letter. TODO for 0.1. Thanks! Maurício _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by John Meacham
John Meacham wrote:
> In particular, a Huffman coding: > http://en.wikipedia.org/wiki/Huffman_coding > is ideal for this (assuming you just are taking advantage of frequency > analysis). A dynamic Huffman Tree will even adapt as it is being used to > whatever the current language is. Huffman Trees are easy and fun to > implement too. > Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing... _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Maurício CA
On Mon, 21 Jun 2010, Maurício CA wrote:
> > > bitspeak is a small proof of concept application that allows > > > writing text using only two commands (yes/no, 1/2, top/down etc.). > > > > There is a parallel between data compression algorithms and this sort of > > task, expressing a sentence in the minimal number of bits via > > compression also minimized the number of yes/no questions that need to > > be asked. > > > > In particular, a Huffman coding: > > Sure, Huffman was actually my first tought. But I couldn't think > of a pratical display for the result of Huffman encoding that > could be easily followed by a human looking at the screen. Tony. -- f.anthony.n.finch <[hidden email]> http://dotat.at/ SOUTH BISCAY: EASTERLY OR NORTHEASTERLY 4 OR 5, OCCASIONALLY 6 IN SOUTHWEST. SLIGHT OR MODERATE. FAIR. GOOD. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Andrew Coppin
On Tue, Jun 22, 2010 at 06:24:22PM +0100, Andrew Coppin wrote:
> John Meacham wrote: >> In particular, a Huffman coding: >> http://en.wikipedia.org/wiki/Huffman_coding >> is ideal for this (assuming you just are taking advantage of frequency >> analysis). A dynamic Huffman Tree will even adapt as it is being used to >> whatever the current language is. Huffman Trees are easy and fun to >> implement too. >> > > Interestingly, Huffman coding is one of those problems with a trivially > simple mathematical expression, which none the less turns out to be > difficult to express succinctly in Haskell. Oh, you can *do* it. It just > seems to take a surprising amount of typing... Hmmm.... Do I hear a challenge? :) Actually, I can't find my huffman code at the moment, I would be curious what others take on the problem was. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
john:
> On Tue, Jun 22, 2010 at 06:24:22PM +0100, Andrew Coppin wrote: > > John Meacham wrote: > >> In particular, a Huffman coding: > >> http://en.wikipedia.org/wiki/Huffman_coding > >> is ideal for this (assuming you just are taking advantage of frequency > >> analysis). A dynamic Huffman Tree will even adapt as it is being used to > >> whatever the current language is. Huffman Trees are easy and fun to > >> implement too. > >> > > > > Interestingly, Huffman coding is one of those problems with a trivially > > simple mathematical expression, which none the less turns out to be > > difficult to express succinctly in Haskell. Oh, you can *do* it. It just > > seems to take a surprising amount of typing... > > Hmmm.... Do I hear a challenge? :) > > Actually, I can't find my huffman code at the moment, I would be > curious what others take on the problem was. > http://hackage.haskell.org/package/huffman A simple and pure Haskell implementation of the Huffman encoding algorithm. Google turns up a lot of results. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Don Stewart wrote:
> http://hackage.haskell.org/package/huffman > > A simple and pure Haskell implementation of the Huffman encoding algorithm. > What the...? Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Tue, Jun 22, 2010 at 4:18 PM, Andrew Coppin <[hidden email]> wrote: What the...? Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had. I would argue that quicksort is considerably simpler, as it doesn't have to maintain an explicit tree, lookup and merge values, deal with bits, etc. For something, perhaps closer in spirit to quicksort, and still compression-oriented, I have an implementation of LZ78 for decompressing streams directly into a monoid, rather than reconstituting the result, which also winds up remarkably terse and a great deal more general than its imperative counter-parts. ;) http://hackage.haskell.org/packages/archive/monoids/0.1.36/doc/html/src/Data-Generator-Compressive-LZ78.html -Edward Kmett _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Andrew Coppin
On Tue, Jun 22, 2010 at 10:18 PM, Andrew Coppin
<[hidden email]> wrote: > Don Stewart wrote: >> >> http://hackage.haskell.org/package/huffman >> >> A simple and pure Haskell implementation of the Huffman encoding >> algorithm. >> > > What the...? > > Oh, I see. It uses another package to handle the tricky sorting and > searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Quicksort is naturally expressed using filter and (++), etc. Huffman coding is naturally expressed in terms of priority queues, etc. Why is using the right vocabulary OK in one case and not in the other? This seems like an example of list-chauvinism -- what Chris Okasaki calls a communal blind spot of the FP community in Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design -- http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps --Max _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Andrew Coppin
G'day all.
Quoting Andrew Coppin <[hidden email]>: > What the...? > > Oh, I see. It uses another package to handle the tricky sorting and > searching stuff. Well, yeah, that would make the code a bit shorter... > ;-) > > Even so, it's not nearly as elegant to behold as, say, the quicksort > algorithm, despite being of roughly similar complexity. Still, it's > shorter than what I had. Ah, but the famous Haskell quicksort algorithm is optimised for brevity. It's an executable specification of quicksort, not a practical sort algorithm. But honestly, it's just not that hard to do in linear time, assuming the symbols are sorted by frequency: data HuffmanTree a = Empty | Node (HuffmanTree a) (HuffmanTree a) | Leaf a deriving Show huffmanTree :: (Ord w, Num w) => [(w,a)] -> HuffmanTree a huffmanTree = build . map (id &&& Leaf) . sortBy (comparing fst) where build [] = Empty build [(_,t)] = t build ((w1,t1):(w2,t2):wts) = build $ insertBy (comparing fst) (w1+w2, Node t1 t2) wts Now if you want a real challenge, implement length-limited Huffman codes. Here's a suggested interface: -- There really should be a better traits typeclass for bit hackery, -- but there isn't. class (Integral w, Bits w) => WordType w where { wordBits :: w -> Int } instance WordType Word8 where { wordBits = 8 } instance WordType Word16 where { wordBits = 16 } instance WordType Word32 where { wordBits = 32 } instance WordType Word64 where { wordBits = 64 } minimalRedundancyCode :: (Ord w, Num w, WordType word) => [(w,a)] -> [(a,Int,word)] -- minimalRedundancyCode returns an optimal prefix-free minimal-redundancy -- code such that every code fits in a word of size w. An entry (a,b,w) -- in the result means that the code for a is stored in the b least -- significant bits of w. Andrew Bromage _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
G'day all.
> But honestly, it's just not that hard to do in linear time, assuming > the symbols are sorted by frequency: Or maybe not so easy. Andrew Bromage _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by ajb@spamcop.net
Hello ajb,
Wednesday, June 23, 2010, 6:58:30 AM, you wrote: > build ((w1,t1):(w2,t2):wts) > = build $ insertBy (comparing fst) (w1+w2, Node t1 t2) wts this algo is O(n^2). to be O(n) you should handle separate lists of leafs and nodes, adding new nodes to the tail of second list -- Best regards, Bulat mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by John Meacham
> From: Max Rabkin <[hidden email]>
> > This seems like an example of list-chauvinism -- what Chris Okasaki > calls a communal blind spot of the FP community in Breadth-First > Numbering: Lessons from a Small Exercise in Algorithm Design -- > http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps > Thanks for sharing; this was an interesting (and short!) read. I would like to see other Haskeller's responses to this problem. I'll restate it here hoping to get replies from those who haven't read the paper yet: Assume you have a type of labeled binary trees: data Tree a = E | T a (Tree a) (Tree a) and you are to produce a function bfnum :: Tree a -> Tree Int that performs a breadth-first numbering of the tree (starting with 1), preserving the tree structure. How would you implement bfnum? (If you've already read the paper, what was your first answer?) For the record, my solution doesn't rely on any other data structures or laziness AFAICT, and I think it would fit into the Level-Oriented category of solutions. John _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
I made (presumably) inefficient huffman algorithm not too long ago:
http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=26484#a26484 I guess it doesn't normally need to be terribly efficient as the result can be stored in a map of some sort. On Wed, Jun 23, 2010 at 10:41 PM, John Lato <[hidden email]> wrote: >> From: Max Rabkin <[hidden email]> >> >> This seems like an example of list-chauvinism -- what Chris Okasaki >> calls a communal blind spot of the FP community in Breadth-First >> Numbering: Lessons from a Small Exercise in Algorithm Design -- >> http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps >> > > Thanks for sharing; this was an interesting (and short!) read. > > I would like to see other Haskeller's responses to this problem. I'll > restate it here hoping to get replies from those who haven't read the > paper yet: > > Assume you have a type of labeled binary trees: > > data Tree a = E | T a (Tree a) (Tree a) > > and you are to produce a function > > bfnum :: Tree a -> Tree Int > > that performs a breadth-first numbering of the tree (starting with 1), > preserving the tree structure. > > How would you implement bfnum? (If you've already read the paper, > what was your first answer?) > > For the record, my solution doesn't rely on any other data structures > or laziness AFAICT, and I think it would fit into the Level-Oriented > category of solutions. > > John > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by John Lato-2
On Wed, Jun 23, 2010 at 03:41:29PM +0100, John Lato wrote:
> How would you implement bfnum? (If you've already read the paper, > what was your first answer?) This was my first answer, and it is wrong, but I thought it was slightly clever, so here it is: bfnum :: Tree a -> Tree Int bfnum tree = bfnum' tree 1 where bfnum' E _ = E bfnum' (T _ l r) i = T i (bfnum' l (i*2)) (bfnum' r ((i*2)+1)) If you have an incomplete tree, it will skip though. I didn't realize it was wrong until I finished reading the paper though, so I don't have a better solution that actually works. -- Daniel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Wed, Jun 23, 2010 at 4:35 PM, Daniel Lyons <[hidden email]> wrote:
> On Wed, Jun 23, 2010 at 03:41:29PM +0100, John Lato wrote: >> How would you implement bfnum? (If you've already read the paper, >> what was your first answer?) > > This was my first answer, and it is wrong, but I thought it was > slightly clever, so here it is: > > bfnum :: Tree a -> Tree Int > bfnum tree = bfnum' tree 1 > where > bfnum' E _ = E > bfnum' (T _ l r) i = T i (bfnum' l (i*2)) (bfnum' r ((i*2)+1)) > > If you have an incomplete tree, it will skip though. > > I didn't realize it was wrong until I finished reading the paper > though, so I don't have a better solution that actually works. > That was my first try too. If this answer did work, I don't think the question would be interesting. John _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |