ANN: bitspeak 0.0.1

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

ANN: bitspeak 0.0.1

Maurí­cio CA
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
Reply | Threaded
Open this post in threaded view
|

Re: ANN: bitspeak 0.0.1

Nils Schweinsberg
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
Reply | Threaded
Open this post in threaded view
|

Re: ANN: bitspeak 0.0.1

Tom Hawkins-2
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
Reply | Threaded
Open this post in threaded view
|

Re: ANN: bitspeak 0.0.1

John Meacham
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
Reply | Threaded
Open this post in threaded view
|

Re: ANN: bitspeak 0.0.1

Maurí­cio CA
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
Reply | Threaded
Open this post in threaded view
|

Re: ANN: bitspeak 0.0.1

Maurí­cio CA
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
Reply | Threaded
Open this post in threaded view
|

Re: ANN: bitspeak 0.0.1

Andrew Coppin
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: ANN: bitspeak 0.0.1

Tony Finch
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.
http://www.inference.phy.cam.ac.uk/dasher/

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
Reply | Threaded
Open this post in threaded view
|

Huffman Codes in Haskell

John Meacham
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

Don Stewart-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

Andrew Coppin
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

Edward Kmett-2

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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

Max Rabkin-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

ajb@spamcop.net
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

ajb@spamcop.net
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
Reply | Threaded
Open this post in threaded view
|

Re[2]: Huffman Codes in Haskell

Bulat Ziganshin-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

John Lato-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

Lyndon Maydwell
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

Daniel Lyons
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
Reply | Threaded
Open this post in threaded view
|

Re: Huffman Codes in Haskell

John Lato-2
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
12