Re: [Haskell-cafe] is there some book about haskell and data struct and alg?

[Gwern Branwen]

On 2008.05.28 20:11:54 -0700, "Benjamin L. Russell" <[EMAIL PROTECTED]> 
scribbled 2.5K characters:
> Although all the source code for the pdf version 
> (http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf) of "Purely Functional Data 
> Structures" is provided in Standard ML, not Haskell, I found a broken link to 
> the supposedly equivalent Haskell source code on "Books - HaskellWiki" 
> (http://haskell.org/haskellwiki/Books):
>
> Haskell source code for the book:
> http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz
>
> Clicking on this link results in the following error:
>
> --
> File Not Found
>
> The requested URL was not found on this web server:
> /~cdo/pfds-haskell.tar.gz
>
> You followed a link from http://haskell.org/haskellwiki/Books
> Contact the maintainer: [no address given].
>
>
>
> Other solutions:
>
> * You may find what you need by performing a search in the main index for 
> this web site.
> * You can perform a Google search on the departmental pages.
>
>
> This Columbia University Computer Science web server, www.cs.columbia.edu,
> is maintained by [no address given]
> --
>
> Without the equivalent Haskell source code, the code must be manually 
> translated from Standard ML into Haskell.  Does anybody know why the link is 
> broken, when it may be fixed, and from where the Haskell source code can be 
> currently obtained?
>
> Benjamin L. Russell

If you are interested in the topic, you will probably want to check out Edison: 
.

I believe some of the older code in there was even written by Okasaki.

--
gwern
EODG Vanuatu bombers BLU- grenades NAVWAN rack Ortega 170kt MI6


signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: appending an element to a list

[Abhay Parvate]

I think I would like to make another note: when we talk about the complexity
of a function, we are talking about the time taken to completely evaluate
the result. Otherwise any expression in haskell will be O(1), since it just
creates a thunk.
And then the user of the program is to be blamed for running the program,
since that is what caused evaluation of those thunks :)


Abhay

2008/5/31 Martin Geisler <[EMAIL PROTECTED]>:

> Tillmann Rendel <[EMAIL PROTECTED]> writes:
>
> Hi! (Cool, another guy from DAIMI on haskell-cafe!)
>
> > Another (n - 1) reduction steps for the second ++ to go away.
> >
> > last ("o" ++ "l")
> > A)  ~>  last ('o' : "" ++ "l"))
> > L)  ~>  last ("" ++ "l")
> > A)  ~>  last ("l")
> > L)  ~>  'l'
> >
> > And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
> > steps. Counting together, we had to use
> >
> >   n + (n - 1) + (n - 2) + ... = n!
> >
> > reduction steps to get rid of the n calls to ++, which lies in O(n^2).
> > Thats what we expected of course, since we know that each of the ++
> > would need O(n) steps.
>
> I really liked the excellent and very clear analysis! But the last
> formula should be:
>
>   n + (n - 1) + (n - 2) + ... = n * (n+1) / 2
>
> which is still of order n^2.
>
> --
> Martin Geisler
>
> VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
> SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Fwd: Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Martin Blais]

FYI.

On Sat, 31 May 2008 02:11:13 +0200, "Daniel Fischer"
<[EMAIL PROTECTED]> said:
> Am Samstag, 31. Mai 2008 02:28 schrieb Martin Blais:
> > Allright, this is a definitely a newbie question.
> >
> > I'm learning Haskell and going through the exercises in the
> > beautiful Hutton book, and one of them requires for me to
> > write a loop that queries a line from the user (stdin),
> > looping until the user enters a valid integer (at least
> > that's how I want to implement the interface to the
> > exercise). I have tried tons of variants and modifications
> > of code, and I can't find the way to implement this. Here is
> > what my emacs buffer is at now::
> >
> >   import Text.Read
> >   import System.IO
> >   import qualified Control.Exception as C
> >
> >   getNum :: IO Int
> >   getNum = do line <- (hGetLine stdin)
> >   x <- (C.catch (do return (read line :: Int)) (\e -> getNum))
> >   return x
> 
> All you need is a little strictness,
>   x <- (C.catch (return $! read line :: Int) (\e -> getNum))
> works. Another option is using evaluate instead of return.
> The problem is that (read line :: Int) is not evaluated until it is
> needed, 
> that is when it's going to be printed, but then it's too late to catch
> the 
> exception.
> 
> Some general remarks:
> hGetLine stdin === getLine
> do x <- action
>return x
> is the same as 
> action
> 
> >
> >   main = do x <- getNum
> > putStr ((show x) ++ "\n")
> 
>   print x
> >
> > Now, I've tried the Prelude's catch, the Control.Exception
> > catch, I've tried moving it at the top of getnum, I've tried
> > without catch, I've tried a ton of other shtuff, so much
> > that I'm starting to think that Emacs is going to run out of
> > electrons soon. I asked some half-newbie friends who are
> > insanely enthousiastic about Haskell and they can't do it
> > either (I'm starting to think that those enthousiastic
> > friends are dating a beautiful girl with 3 PhDs, but she has
> > a 2-inch thick green and gooey wart smack on her nose and
> > they're so blindly in love that they can't admit that she
> > does). I've asked some university profs and they sidetrack
> > my question by saying I shouldn't do I/O so early. Can
> > anyone here restore my faith in the Haskell section of
> > humanity?
> >
> > 1. How do I catch the exception that is raised from "read"?
> 
> By forcing the evaluation.
> >
> > 2. Where do I find the appropriate information I need in
> >order to fix this? I'm probably just not searching in the
> >right place. (Yes, I've seen the GHC docs, and it doesn't
> >help, maybe I'm missing some background info.)
> 
> Get used to lazy evaluation, the Hutton book should contain a chapter
> about 
> that.
> 
> >
> > 3. Please do not tell me I should solve the problem
> >differently. Here is the problem I'm trying to solve, and
> >nothing else:
> >
> >  "Write a program that reads a line from the user,
> >  looping the query until the line contains a valid
> >  integer."
> >
> > It shouldn't be too hard i think. The best answer would be a
> > two-liner code example that'll make me feel even more stupid
> > than I already do.
> >
> > Thanks in advance.
> >
> 
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Martin Blais]

On Fri, 30 May 2008 17:19:54 -0700, "Philip Weaver"
<[EMAIL PROTECTED]> said:
> > Dear Philip, could you point your virtual finger towards a
> > reference/paper/book/any-bleeping-thing that would help this simple
> > beginner understand why it doesn't work in this case? I'm trying to
> > picture why a "read" function that terminates the program would be
> > useful anywhere. In fact, any library function other than something like
> > UNIX's "exit" or "kill" which terminates my program is not really
> > welcome in any of my computer programs, but then again, I haven't yet
> > been illuminated by the genie of pure functional languages.  A reference
> > would be awesome.
> >
> Sorry, I wouldn't know where to point you, other than stating the
> simple rule that you can't catch exceptions in pure code.  Others may
> be able to enlighten you better.
> 
> By the way, the example that Dons gave may look more verbose, but
> (when possible) it's a probably a better idea to capture failure in a
> Maybe than in IO.  I gave you "readIO" because it fit in to the
> exception handling that you were trying to do, and because you said
> you didn't want anyone to tell you you were doing things wrong :).

Here is a private reply from another user, which is more explanatory,
the problem was that the read function wasn't getting called at a point
where it could have been caught (I'll have to look into that into more
detail):


All you need is a little strictness,
x <- (C.catch (return $! read line :: Int) (\e -> getNum))
works. Another option is using evaluate instead of return.
The problem is that (read line :: Int) is not evaluated until it is
needed,
that is when it's going to be printed, but then it's too late to catch
the
exception.

Some general remarks:
hGetLine stdin === getLine
do x <- action
   return x
is the same as
action




___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Philip Weaver]

On Fri, May 30, 2008 at 5:14 PM, Martin Blais <[EMAIL PROTECTED]> wrote:
> On Fri, 30 May 2008 16:54:18 -0700, "Philip Weaver"
> <[EMAIL PROTECTED]> said:
>> > 1. How do I catch the exception that is raised from "read"?
>> >
>> I think you want readIO, which yields a computation in the IO monad,
>> so it can be caught.
>
> Holy schmoly, there it is, words of wisdom, written as clearly as can
> be, from the docs:
>
>  The readIO function is similar to read except that it signals parse
>  failure to the IO monad instead of terminating the program.
>
> I'll be prosternating on the floor towards my web browser for the next
> four hours.
> Thank you very much Philip.
>
> (And thank you Don for the verbose examples.)
>
>
>
>> > 2. Where do I find the appropriate information I need in
>> >   order to fix this? I'm probably just not searching in the
>> >   right place. (Yes, I've seen the GHC docs, and it doesn't
>> >   help, maybe I'm missing some background info.)
>> >
>> In this particular case, I am not sure where you'd find this
>> information.  It's not very intuitive to a beginner why "read" doesn't
>> work in this case.
>
> Dear Philip, could you point your virtual finger towards a
> reference/paper/book/any-bleeping-thing that would help this simple
> beginner understand why it doesn't work in this case? I'm trying to
> picture why a "read" function that terminates the program would be
> useful anywhere. In fact, any library function other than something like
> UNIX's "exit" or "kill" which terminates my program is not really
> welcome in any of my computer programs, but then again, I haven't yet
> been illuminated by the genie of pure functional languages.  A reference
> would be awesome.
>
Sorry, I wouldn't know where to point you, other than stating the
simple rule that you can't catch exceptions in pure code.  Others may
be able to enlighten you better.

By the way, the example that Dons gave may look more verbose, but
(when possible) it's a probably a better idea to capture failure in a
Maybe than in IO.  I gave you "readIO" because it fit in to the
exception handling that you were trying to do, and because you said
you didn't want anyone to tell you you were doing things wrong :).

>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Martin Blais]

On Fri, 30 May 2008 16:54:18 -0700, "Philip Weaver"
<[EMAIL PROTECTED]> said:
> > 1. How do I catch the exception that is raised from "read"?
> >
> I think you want readIO, which yields a computation in the IO monad,
> so it can be caught.

Holy schmoly, there it is, words of wisdom, written as clearly as can
be, from the docs:

  The readIO function is similar to read except that it signals parse
  failure to the IO monad instead of terminating the program.

I'll be prosternating on the floor towards my web browser for the next
four hours. 
Thank you very much Philip.

(And thank you Don for the verbose examples.)



> > 2. Where do I find the appropriate information I need in
> >   order to fix this? I'm probably just not searching in the
> >   right place. (Yes, I've seen the GHC docs, and it doesn't
> >   help, maybe I'm missing some background info.)
> >
> In this particular case, I am not sure where you'd find this
> information.  It's not very intuitive to a beginner why "read" doesn't
> work in this case.

Dear Philip, could you point your virtual finger towards a
reference/paper/book/any-bleeping-thing that would help this simple
beginner understand why it doesn't work in this case? I'm trying to
picture why a "read" function that terminates the program would be
useful anywhere. In fact, any library function other than something like
UNIX's "exit" or "kill" which terminates my program is not really
welcome in any of my computer programs, but then again, I haven't yet
been illuminated by the genie of pure functional languages.  A reference
would be awesome.


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] is there some book about haskell and data struct and alg?

[John Melesky]

On May 30, 2008, at 5:32 AM, Benjamin L. Russell wrote:
Actually, the link now points to the following URL (updated by John  
Melesky):


http://www.eecs.usma.edu/webs/people/okasaki/pfds-haskell.tar.gz

instead of the following URL (set by Henk-Jan van Tuyl):

http://web.archive.org/web/2818044004/http://www.cs.columbia.edu/ 
~cdo/pfds-haskell.tar.gz


I just tested both, and they both seem to work.  Perhaps both should  
be listed, or should we agree on just one?


I chose one over the other because it's the link the author (of the  
original book and of the code) provides from his (new) homepage. And  
because taxing archive.org when a valid alternative is available seems  
like poor form.


This is a problem in general with Haskell code, though, since such a  
large portion of it is created by professors or current students: if/ 
when they leave their current college/university, the links tend to  
break. I don't know that there's a solution except vigilance.


-john


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Don Stewart]

philip.weaver:
> >
> > 1. How do I catch the exception that is raised from "read"?
> >
> I think you want readIO, which yields a computation in the IO monad,
> so it can be caught.

Ah, that's a third option, sequence the effect using readIO,

import System.IO
import qualified Control.Exception as C

main = do
x <- getNum
print x

getNum :: IO Integer
getNum = do
y <- maybeRead
case y of
Nothing -> getNum
Just n  -> return n

maybeRead :: Read a => IO (Maybe a)
maybeRead = C.catch
(do x <- getLine
n <- readIO x
return (Just n)) -- ensure any exception is thrown here
(const (return Nothing))

-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Don Stewart]

blais:
> Allright, this is a definitely a newbie question.
> 
> I'm learning Haskell and going through the exercises in the
> beautiful Hutton book, and one of them requires for me to
> write a loop that queries a line from the user (stdin),
> looping until the user enters a valid integer (at least
> that's how I want to implement the interface to the
> exercise).
  
> 1. How do I catch the exception that is raised from "read"?

The best thing to do is bypass read and use 'reads' to define your
own safe read.

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
[(x, "")] -> Just x
_ -> Nothing


For example, yielding:


import System.IO

main = do
x <- getNum
print x

getNum :: IO Integer
getNum = do
n <- getLine
case maybeRead n of
Nothing -> getNum
Just n  -> return n

> 2. Where do I find the appropriate information I need in
>order to fix this? I'm probably just not searching in the
>right place. (Yes, I've seen the GHC docs, and it doesn't
>help, maybe I'm missing some background info.)

I think Control.Exception.catch should be fine here.
  
> 3. Please do not tell me I should solve the problem
>differently. Here is the problem I'm trying to solve, and
>nothing else:
> 
>  "Write a program that reads a line from the user,
>  looping the query until the line contains a valid
>  integer."
> 
> It shouldn't be too hard i think. The best answer would be a
> two-liner code example that'll make me feel even more stupid
> than I already do.

Of course, it's easy. You can have fun now abstracting out the loop
form in getNum using say, MaybeT or friends. But a loop is simple and easy.

If you want to write it with explict exception handling of the
read parse failure, it's more tedious, as you need to ensure
the read exception is thrown within the body of the enclosing catch.

For example,

import System.IO
import qualified Control.Exception as C

main = do
x <- getNum
print x

getNum :: IO Integer
getNum = do
y <- maybeRead
case y of
Nothing -> getNum
Just n  -> return n

maybeRead :: Read a => IO (Maybe a)
maybeRead = C.catch
(do x <- getLine
let n = read x
n `seq` return (Just n)) -- ensure any exception is thrown here
(const (return Nothing))

-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Philip Weaver]

On Fri, May 30, 2008 at 5:28 PM, Martin Blais <[EMAIL PROTECTED]> wrote:
> Allright, this is a definitely a newbie question.
>
> I'm learning Haskell and going through the exercises in the
> beautiful Hutton book, and one of them requires for me to
> write a loop that queries a line from the user (stdin),
> looping until the user enters a valid integer (at least
> that's how I want to implement the interface to the
> exercise). I have tried tons of variants and modifications
> of code, and I can't find the way to implement this. Here is
> what my emacs buffer is at now::
>
>  import Text.Read
>  import System.IO
>  import qualified Control.Exception as C
>
>  getNum :: IO Int
>  getNum = do line <- (hGetLine stdin)
>  x <- (C.catch (do return (read line :: Int)) (\e -> getNum))
>  return x
>
>  main = do x <- getNum
>putStr ((show x) ++ "\n")
>
> Now, I've tried the Prelude's catch, the Control.Exception
> catch, I've tried moving it at the top of getnum, I've tried
> without catch, I've tried a ton of other shtuff, so much
> that I'm starting to think that Emacs is going to run out of
> electrons soon. I asked some half-newbie friends who are
> insanely enthousiastic about Haskell and they can't do it
> either (I'm starting to think that those enthousiastic
> friends are dating a beautiful girl with 3 PhDs, but she has
> a 2-inch thick green and gooey wart smack on her nose and
> they're so blindly in love that they can't admit that she
> does). I've asked some university profs and they sidetrack
> my question by saying I shouldn't do I/O so early. Can
> anyone here restore my faith in the Haskell section of
> humanity?
>
> 1. How do I catch the exception that is raised from "read"?
>
I think you want readIO, which yields a computation in the IO monad,
so it can be caught.

> 2. Where do I find the appropriate information I need in
>   order to fix this? I'm probably just not searching in the
>   right place. (Yes, I've seen the GHC docs, and it doesn't
>   help, maybe I'm missing some background info.)
>
In this particular case, I am not sure where you'd find this
information.  It's not very intuitive to a beginner why "read" doesn't
work in this case.

> 3. Please do not tell me I should solve the problem
>   differently. Here is the problem I'm trying to solve, and
>   nothing else:
>
> "Write a program that reads a line from the user,
> looping the query until the line contains a valid
> integer."
>
> It shouldn't be too hard i think. The best answer would be a
> two-liner code example that'll make me feel even more stupid
> than I already do.
>
> Thanks in advance.
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] [Newbie question] -- Looping stdin until condition is met

[Martin Blais]

Allright, this is a definitely a newbie question.

I'm learning Haskell and going through the exercises in the
beautiful Hutton book, and one of them requires for me to
write a loop that queries a line from the user (stdin),
looping until the user enters a valid integer (at least
that's how I want to implement the interface to the
exercise). I have tried tons of variants and modifications
of code, and I can't find the way to implement this. Here is
what my emacs buffer is at now::

  import Text.Read
  import System.IO
  import qualified Control.Exception as C

  getNum :: IO Int
  getNum = do line <- (hGetLine stdin)
  x <- (C.catch (do return (read line :: Int)) (\e -> getNum))
  return x

  main = do x <- getNum
putStr ((show x) ++ "\n")

Now, I've tried the Prelude's catch, the Control.Exception
catch, I've tried moving it at the top of getnum, I've tried
without catch, I've tried a ton of other shtuff, so much
that I'm starting to think that Emacs is going to run out of
electrons soon. I asked some half-newbie friends who are
insanely enthousiastic about Haskell and they can't do it
either (I'm starting to think that those enthousiastic
friends are dating a beautiful girl with 3 PhDs, but she has
a 2-inch thick green and gooey wart smack on her nose and
they're so blindly in love that they can't admit that she
does). I've asked some university profs and they sidetrack
my question by saying I shouldn't do I/O so early. Can
anyone here restore my faith in the Haskell section of
humanity?

1. How do I catch the exception that is raised from "read"?

2. Where do I find the appropriate information I need in
   order to fix this? I'm probably just not searching in the
   right place. (Yes, I've seen the GHC docs, and it doesn't
   help, maybe I'm missing some background info.)

3. Please do not tell me I should solve the problem
   differently. Here is the problem I'm trying to solve, and
   nothing else:

 "Write a program that reads a line from the user,
 looping the query until the line contains a valid
 integer."

It shouldn't be too hard i think. The best answer would be a
two-liner code example that'll make me feel even more stupid
than I already do.

Thanks in advance.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Bit Connor]

Yeah, this sounds really similar to functionally reactive programming.

I recommend you start by reading this paper:

http://haskell.cs.yale.edu/frp/genuinely-functional-guis.pdf

On Fri, May 30, 2008 at 11:34 AM, Wolfgang Jeltsch
<[EMAIL PROTECTED]> wrote:
> Am Freitag, 30. Mai 2008 16:09 schrieb Robin Green:
>> […]
>
>> I'm primarily interested in embedded system and desktop UIs,
>
> Than you should take a look at .
>
>> […]
>
> Best wishes,
> Wolfgang
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters

[Achim Schneider]

Bryan O'Sullivan <[EMAIL PROTECTED]> wrote:

> A Bloom filter is a probabilistic data
> structure that provides a fast set membership querying capability.
> It does not give false negatives, but has a tunable false positive
> rate.  (A false positive arises when the filter claims that an
> element is present, but in fact it is not.)
> 
/me squints.

Please tell me that this isn't reversible.

-- 
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited. 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters

[Bryan O'Sullivan]

I'm pleased to announce the availability of a fast Bloom filter library
for Haskell.  A Bloom filter is a probabilistic data structure that
provides a fast set membership querying capability.  It does not give
false negatives, but has a tunable false positive rate.  (A false
positive arises when the filter claims that an element is present, but
in fact it is not.)

The library is easy to use.  As an example, here's a reimplementation of
the Unix "spell" command.

import Data.BloomFilter.Easy (easyList, elemB)

main = do
  filt <- (easyList 0.01 . words) `fmap` readFile "dictionary.txt"
  let check word | word `elemB` filt = ""
 | otherwise = word ++ "\n"
  interact (concat . map check . lines)

It is also carefully tuned for performance.  On my laptop, I can sustain
a construction or query rate well in excess of a million ByteStrings per
second.

Source code:

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bloomfilter

Latest bits:

darcs get http://darcs.serpentine.com/bloomfilter

http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHCi panic

[Don Stewart]

andrewcoppin:
> I don't suppose this will surprise anybody greatly, but...
> 
> Apparently if you write a Haskell module that is 400 KB in size and 
> defines a single CAF consisting of a 45,000-element [String], GHCi 
> panics when attempting to load it interpretted, and hits a stack 
> overflow attempting to load it compiled.
> 
> GHC also takes forever to compile it in the first place, and eventually 
> spits out a 5 MB interface file later followed by a 16 MB object file. 
> And attempting to compile a trivial module against it again causes a 
> stack overflow.
> 
> Presumably the designers of GHC just didn't expect anybody to try to do 
> anything this weird? ;-)
> 
> I was hoping that doing things this way round would be *more efficient*. 
> But this is apparently not the case at all, so I'll just go back to 
> reading the file at runtime instead...
> 
> [Presumably if I was desparate I could convert the data into some kind 
> of preinitialised C structure and manually link it in - if I was that 
> determined.]

As usual, consult the wiki first.

http://haskell.org/haskellwiki/Compiling_in_constants

-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] GHCi panic

[Andrew Coppin]

I don't suppose this will surprise anybody greatly, but...

Apparently if you write a Haskell module that is 400 KB in size and 
defines a single CAF consisting of a 45,000-element [String], GHCi 
panics when attempting to load it interpretted, and hits a stack 
overflow attempting to load it compiled.


GHC also takes forever to compile it in the first place, and eventually 
spits out a 5 MB interface file later followed by a 16 MB object file. 
And attempting to compile a trivial module against it again causes a 
stack overflow.


Presumably the designers of GHC just didn't expect anybody to try to do 
anything this weird? ;-)


I was hoping that doing things this way round would be *more efficient*. 
But this is apparently not the case at all, so I'll just go back to 
reading the file at runtime instead...


[Presumably if I was desparate I could convert the data into some kind 
of preinitialised C structure and manually link it in - if I was that 
determined.]


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: appending an element to a list

[Martin Geisler]

Tillmann Rendel <[EMAIL PROTECTED]> writes:

Hi! (Cool, another guy from DAIMI on haskell-cafe!)

> Another (n - 1) reduction steps for the second ++ to go away.
>
> last ("o" ++ "l")
> A)  ~>  last ('o' : "" ++ "l"))
> L)  ~>  last ("" ++ "l")
> A)  ~>  last ("l")
> L)  ~>  'l'
>
> And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
> steps. Counting together, we had to use
>
>   n + (n - 1) + (n - 2) + ... = n!
>
> reduction steps to get rid of the n calls to ++, which lies in O(n^2).
> Thats what we expected of course, since we know that each of the ++
> would need O(n) steps.

I really liked the excellent and very clear analysis! But the last
formula should be:

   n + (n - 1) + (n - 2) + ... = n * (n+1) / 2

which is still of order n^2.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.


pgpxgbfpNjJtq.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Damnit, we need a CPAN.

[Achim Schneider]

Wolfgang Jeltsch <[EMAIL PROTECTED]> wrote:

> Am Donnerstag, 29. Mai 2008 17:38 schrieb Achim Schneider:
> > […]
> 
> > Rationale: We need […] grapefruit authors that commit to hackage
> 
> Our reason to not commtting Grapefruit to Hackage so far was that
> this would mean making an official release and we thought that
> Grapefruit is not yet ready for this.  However, I might be wrong in
> the sense that also despite its current deficiencies, Grapefruit
> should be available from Hackage.  What do you think?
> 
Release early, release often. 
http://catb.org/~esr/writings/cathedral-bazaar/cathedral-bazaar/ar01s04.html

> By the way, it’s nice to hear that there are people which are really 
> interested in trying Grapefruit out.  It still makes me wonder at
> times that I’ve made something that other people find really useful.
> (Of course, I’ve not done Grapefruit alone but Matthias Reisner has
> also done a notable amount of work.)  So I would really like to get
> feedback concerning peoples impressions about Grapefruit.  Seeing
> interest in Grapefruit might give me more motivation for the work on
> it and therefore speed up its development.
> 
I'm generally very interested in declarative GUI programming, but not
nearly enough acquainted with the whole topic to judge one project's
approach over the other. I just followed standard scientific evaluation
technique to select the projects to consider: The ones with the most and
most recent activity win.

So far, my impression is that documentation is severely lacking, but
then I'm too busy watching Babylon 5 right now and did not get more
than half an hour or so looking at grapefruit.

-- 
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited. 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: Damnit, we need a CPAN.

[Duncan Coutts]

On Fri, 2008-05-30 at 16:33 +0200, Chaddaï Fouché wrote:
> 2008/5/30 Achim Schneider <[EMAIL PROTECTED]>:
> > I already was pleasantly surprised when discovering cabal-install, I
> > think it deserves some more prominence, or even integration into cabal
> > itself, to make everyone aware of the fact that there's such a thing as
> > automatic installation and tempt people to make it work.
> 
> I completely agree, cabal-install is very nice, and should be more widely 
> known.

Fear not, we are working towards a release :-)

In fact in just the last couple days I've committed a new dependency
resolver which should solve the dreaded diamond dependency problem:
http://blog.well-typed.com/2008/04/the-dreaded-diamond-dependency-problem/

It can, for example, construct valid install plans for yi.

There are a few more bits to clean up before I enable it by default and
ask for wider testing.

Duncan

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] appending an element to a list

[Tillmann Rendel]

Lanny Ripple wrote:

My $0.02 is to say

-- O(1) longList ++ [5]

Yay.  I've got a thunk.  Oh wait, I need to access the '5'?  No 
different than doing so for


-- O(n) until ((==5) . head) [l,o,n,g,L,i,s,t,5]

It's not the (++) that's O(n).  It's the list traversal.


Lets look at the actual reductions going on. To make the example easier,
I would like to use last instead of your complicated until. It shouldn't
make a difference.

Lets look at the reduction of (last "longList") to whnf first:

L)  last "longList"
L)  ~>  last "ongList"
L)  ~>  last "ngList"
L)  ~>  last "gList"
L)  ~>  last "List"
L)  ~>  last "ist"
L)  ~>  last "st"
L)  ~>  last "t"
~>  't'

The L prefixed marks all lines which are reduced by calls to last.
Clearly, we need n reduction steps here.

Now, what about last ("longList" ++ "!")?

A)  last ("longList" ++ "!")
L)  ~>  last ('l' : ("ongList" ++ "!"))
A)  ~>  last ("ongList" ++ "!")
L)  ~>  last ('o' : ("ngList" ++ "!"))
A)  ~>  last ("ngList" ++ "!")
L)  ~>  last ('n' : ("gList" ++ "!"))
A)  ~>  last ("gList" ++ "!")
L)  ~>  last ('g' : ("List" ++ "!"))
A)  ~>  last ("List" ++ "!")
L)  ~>  last ('L' : ("ist" ++ "!"))
A)  ~>  last ("ist" ++ "!")
L)  ~>  last ('i' : ("st" ++ "!"))
A)  ~>  last ("st" ++ "!")
L)  ~>  last ('s' : ("t" ++ "!"))
A)  ~>  last ("t" ++ "!")
L)  ~>  last ('t' : ("" ++ "!"))
A)  ~>  last ("" ++ "!")
L)  ~>  last "!"
~>  '!'

Calls to ++ are marked with A (for append). Now, we have to reduce a
call to ++ everytime before we can reduce a call to last, so we have

n steps for calls of last as before
  + n steps for interleaved calls of ++
  + 1 step for the final call of ++
  + 1 step for the final call of last
  = 2n + 2 steps in total

The difference between (2n + 2) and (n) is (n + 2) and lies clearly in
O(n). So, by the addition of ++ "!" to our program, we had to do O(n)
reduction steps more.

Since we had to do O(n) reductions steps anyway, this didn't show up in
the overall complexity, but our program is only half as fast,
instead of constant amount slower, which seems to make a difference to me.

And other programs could suffer even more badly, since their complexity
could go up, e.g., from O(n) to O(n^2). A simple example is this naive
reverse function:

  reverse [] = []
  reverse (x:xs) = reverse xs ++ [x]

let's see how (last (reverse "long")) is reduced to whnf. I will not
even attempt "longList" ...

R)  last (reverse "long")
R)  ~>  last (reverse "ong" ++ "l")
R)  ~>  last ((reverse "ng" ++ "o") ++ "l")
R)  ~>  last (((reverse "g" ++ "n") ++ "o") ++ "l")
R)  ~>  last reverse "" ++ "g") ++ "n") ++ "o") ++ "l")
R)  ~>  last "" ++ "g") ++ "n") ++ "o") ++ "l")

At this point, we have reduced reverse in n steps to an expression
containing n calls to ++. If ++ were O(1), we would need only O(n)
additional steps to finish the job. But see what happens:

last "" ++ "g") ++ "n") ++ "o") ++ "l")
A)  ~>  last ((("g" ++ "n") ++ "o") ++ "l")

The first ++ was easy, only 1 reduction step.

last ((("g" ++ "n") ++ "o") ++ "l")
A)  ~>  last ((('g' : ("" ++ "n")) ++ "o") ++ "l")
A)  ~>  last (('g' : (("" ++ "n") ++ "o")) ++ "l")
A)  ~>  last ('g' : ((("" ++ "n") ++ "o") ++ "l"))
L)  ~>  last ((("" ++ "n") ++ "o") ++ "l")
A)  ~>  last (("n" ++ "o") ++ "l")

Oups, for the second ++, we needed n reduction steps to move the first
char out of all these nested ++'s.

last (("n" ++ "o") ++ "l")
A)  ~>  last (('n' : ("" ++ "o")) ++ "l")
A)  ~>  last ('n' : (("" ++ "o") ++ "l"))
L)  ~>  last (("" ++ "o") ++ "l")
A)  ~>  last ("o" ++ "l")

Another (n - 1) reduction steps for the second ++ to go away.

last ("o" ++ "l")
A)  ~>  last ('o' : "" ++ "l"))
L)  ~>  last ("" ++ "l")
A)  ~>  last ("l")
L)  ~>  'l'

And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
steps. Counting together, we had to use

  n + (n - 1) + (n - 2) + ... = n!

reduction steps to get rid of the n calls to ++, which lies in O(n^2).
Thats what we expected of course, since we know that each of the ++
would need O(n) steps.


I can further beat this pedantic point to death by pointing out there
is no difference between

longList ++ [5]

and

longList ++ (repeat 5)

Getting to the first 5 is still O(n).


That's a different question. For the complexity of ++, the right-hand
side operand is irrelevant. The n means the length of the left-hand side
operand here.

  Tillmann
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Lazy lists simulated by unboxed mutable arrays

[Henning Thielemann]

On Wed, 28 May 2008, Ketil Malde wrote:


Bulat Ziganshin <[EMAIL PROTECTED]> writes:


well, i don't understand difference between your idea and lazybs
implementation


HT said earlier that:


This would still allow the nice tricks for recursive Fibonacci
sequence definition.


Which I guess refers to something like:

 fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

I don't think you can do that with LBS, since you'd need to calculate
a whole chunk at a time, and for any chunk size > 1, each chunk
depends on itself.


I have now implemented a small prototype:
  http://code.haskell.org/storablevector/Data/StorableVector/Cursor.hs

Actually you can run the Fibonacci example but it allocates three arrays:
  let f2 = zipNWith 15 (+) f0 f1; f1 = cons 1 f2; f0 = cons (0::Int) f1 in f0

I'm afraid the compiler cannot optimize the IORefs to unboxed values, even 
in registers, because in principle they can be modified from everywhere in 
the program. Is there a better way than using IORefs hidden by 
unsafePerformIO?




{-# OPTIONS_GHC -cpp -fglasgow-exts #-}
{- |
Simulate a list with strict elements by a more efficient array structure.
-}
module Data.StorableVector.Cursor where

import Control.Exception(assert, )
import Control.Monad.State  (StateT(StateT), runStateT, )
import Data.IORef   (IORef, newIORef, readIORef, writeIORef, )

import Foreign.Storable (Storable(peekElemOff, pokeElemOff))
import Foreign.ForeignPtr   (ForeignPtr, mallocForeignPtrArray, 
withForeignPtr, )

import Control.Monad(when)
import Data.Maybe   (isNothing)

import System.IO.Unsafe (unsafePerformIO)

import Data.StorableVector.Utility (viewListL, mapSnd, )

import Prelude hiding (length, foldr, zipWith, )


-- | Cf. StreamFusion  Data.Stream
data Generator a =
   forall s. -- Seq s =>
  Generator {
 next  :: {-# UNPACK #-} !(StateT s Maybe a),  -- compute next value
 state :: {-# UNPACK #-} !(IORef (Maybe s))-- current state
  }

{- |
This simulates a
@ data StrictList a = Elem !a (StrictList a) | End @
by an array and some unsafe hacks.
-}
data Buffer a =
   Buffer {
   memory :: {-# UNPACK #-} !(ForeignPtr a),
   size   :: {-# UNPACK #-} !Int,  -- size of allocated memory
   gen:: {-# UNPACK #-} !(Generator a),
   cursor :: {-# UNPACK #-} !(IORef Int)
   }

{- |
Vector is a part of a buffer.
-}
data Vector a =
   Vector {
   buffer :: {-# UNPACK #-} !(Buffer a),
   start  :: {-# UNPACK #-} !Int,   -- invariant: start <= cursor
   maxLen :: {-# UNPACK #-} !Int-- invariant: start+maxLen <= size
   }


-- * construction

{-# INLINE create #-}
create :: (Storable a) => Int -> Generator a -> Buffer a
create l g = unsafePerformIO (createIO l g)

-- | Wrapper of mallocForeignPtrArray.
createIO :: (Storable a) => Int -> Generator a -> IO (Buffer a)
createIO l g = do
fp <- mallocForeignPtrArray l
cur <- newIORef 0
return $! Buffer fp l g cur


{- |
@ unfoldrNTerm 20  (\n -> Just (n, succ n)) 'a' @
-}
unfoldrNTerm :: (Storable b) =>
   Int -> (a -> Maybe (b, a)) -> a -> Vector b
unfoldrNTerm i f x0 =
   unsafePerformIO (unfoldrNTermIO i f x0)

unfoldrNTermIO :: (Storable b) =>
   Int -> (a -> Maybe (b, a)) -> a -> IO (Vector b)
unfoldrNTermIO i f x0 =
   do ref <- newIORef (Just x0)
  buf <- createIO i (Generator (StateT f) ref)
  return (Vector buf 0 i)


{-# INLINE pack #-}
pack :: (Storable a) => Int -> [a] -> Vector a
pack n = unfoldrNTerm n viewListL


{-# INLINE cons #-}
{- |
This is expensive and should not be used to construct lists iteratively!
-}
cons :: Storable a =>
   a -> Vector a -> Vector a
cons x xs =
   unfoldrNTerm (succ (maxLen xs))
  (\(mx0,xs0) ->
  fmap (mapSnd ((,) Nothing)) $
  maybe
 (viewL xs0)
 (\x0 -> Just (x0, xs0))
 mx0) $
   (Just x, xs)


{-# INLINE zipWith #-}
zipWith :: (Storable a, Storable b, Storable c) =>
   (a -> b -> c) -> Vector a -> Vector b -> Vector c
zipWith f ps0 qs0 =
   zipNWith (min (maxLen ps0) (maxLen qs0)) f ps0 qs0


{-# INLINE zipNWith #-}
zipNWith :: (Storable a, Storable b, Storable c) =>
   Int -> (a -> b -> c) -> Vector a -> Vector b -> Vector c
zipNWith n f ps0 qs0 =
   unfoldrNTerm n
  (\(ps,qs) ->
 do (ph,pt) <- viewL ps
(qh,qt) <- viewL qs
return (f ph qh, (pt,qt)))
  (ps0,qs0)



-- * inspection

-- | evaluate next value in a buffer
advanceIO :: Storable a =>
   Buffer a -> IO ()
advanceIO (Buffer p sz (Generator n s) cr) =
   do c <- readIORef cr
  assert (c < sz) $
 do writeIORef cr (succ c)
ms <- readIORef s
case ms of
   Nothing -> return ()
   Just s0 ->
  case runStateT n s0 of
 Nothing -> writeIORef s Nothing
 Just (a,s1) ->
writeIORef s (Just s1) >>
withForeignPtr p (\q 

Re: [Haskell-cafe] test driving cabal install... cabal install and normal install (runghc Setup) don't mix... two package.conf files...

[Thomas Hartman]

I think the reason it took longer to build HAppS-Server is that
previously, when I was installing the MyProject example from happs.org
I was using searchpath.

I guess searchpath doesn't compile every single haskell module,
whereas runghc Setup build and cabal install does.

2008/5/29 Spencer Janssen <[EMAIL PROTECTED]>:
> On Thu, May 29, 2008 at 06:11:04PM -0700, Thomas Hartman wrote:
>> After a little drama with zlib, I managed to get cabal-install installed.
>>
>> I then attempted to do
>>
>> cabal install HAppS-Server
>>
>> since this is a module with a lot of dependencies, and in rapid
>> development flux, so perenially painful for me to install.
>>
>> The result is that I managed to install everything up to HAppS-State,
>> which I think is the last dependency, but then seemed to hang
>> indefinitely in the middle of installing HAppS-Server at the end.
>>
>> OK, I thought, then perhaps I can do normal runghc Setup.hs after
>> downloading and unzipping the tar from
>>
>> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HAppS-Server-0.9.2.1
>>
>> However, this resulted in error
>>
>> [EMAIL PROTECTED]:~/haskellInstalls/smallInstalls/HAppS-Server-0.9.2.1>runghc
>> Setup.hs configure
>> ...
>> Setup.hs: At least the following dependencies are missing:
>> HAppS-Data >=0.9.2...
>>
>> Strange, because I had just installed that module via cabal-install,
>> and I could load it in ghci with :m +HappS.Data.
>
> 'cabal install' installs packages to your user database by default.  However,
> 'Setup configure' only uses packages from the global database unless the 
> --user
> flag is passed.
>
>> I then ran ghc-pkg and got this strange result that my packages were
>> broken into two different files. Is this by design?
>>
>> ghc-pkg list
>> /usr/local/lib/ghc-6.8.2/package.conf:
>> Cabal-1.2.3.0, Cabal-1.3.11, Cabal-1.5.2, DeepArrow-0.2,
>> 
>> /home/thartman/.ghc/i386-linux-6.8.2/package.conf:
>> HAppS-Data-0.9.2.1, HAppS-IxSet-0.9.2.1, HAppS-State-0.9.2.1,
>
> Yep, this is by design.  The first is a global database that will require root
> access to modify.  The second is your user database which you can modify
> without root access.
>
>> I am curious if anybody else is able to install HAppS-Server using
>> cabal install, and whether they can shed any light on the other isuses
>> I raised.
>>
>> Thomas.
>
> I tried building HAppS-server the other day, and had a similar experience.  It
> seems that HAppS uses some incredibly elaborate TH/typeclass hacks that take
> gobs of resources to compile -- my box actually ran out of memory attempting 
> to
> build it.
>
>
> Cheers,
> Spencer Janssen
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: [Haskell] Announce: hback - dual n-back memory game (0.0.2)

[Don Stewart]

wojtowicz.norbert:
> I'm pleased to publically announce a little project I've worked on.
> Based on a recent research paper [0] that claims fluid intelligence
> could be improved by training working memory, I wrote up a dual n-back
> test memory game in Haskell and gtk2hs. This is still essentially an
> alpha release: all comments are most welcome.
> 
> Original post (includes gameplay instructions):
> http://pithyless.com/blog/2008/05/18/hback-haskell-n-back-memory-game/
> 
> Updated version (overhaul of game with some feature updates):
> http://pithyless.com/blog/2008/05/30/hback-0_0_2/
> 
> Cabal file can be found on hackage:
> http://hackage.haskell.org/packages/archive/hback/0.0.2/hback-0.0.2.tar.gz
> 
> [0] http://www.pnas.org/cgi/content/abstract/0801268105v1

Awesome!

Is this the first real implementation of the game described in the
paper? If so, that's a bit of a coup.

Good work by the GTK team that has made these gui things in Haskell so
easy.

-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] appending an element to a list

[Lanny Ripple]

My $0.02 is to say

  -- O(1)
  longList ++ [5]

Yay.  I've got a thunk.  Oh wait, I need to access the '5'?  No
different than doing so for

  -- O(n)
  until ((==5) . head) [l,o,n,g,L,i,s,t,5]

It's not the (++) that's O(n).  It's the list traversal.  I can
further beat this pedantic point to death by pointing out there is
no difference between

  longList ++ [5]

and

  longList ++ (repeat 5)

Getting to the first 5 is still O(n).

  Cheers,
  -ljr


Tillmann Rendel wrote:
> 
> 
> Adrian Neumann wrote:
>> Hello,
>>
>> I was wondering how expensive appending something to a list really is.
>> Say I write
>>
>> I'd say "longList ++ [5]" stays unevaluated until I consumed the whole
>> list and then appending should go in O(1). Similarly when
>> concatenating two lists.
>>
>> Is that true, or am I missing something?
> 
> I think that is true and you are missing something: You have to push the
> call to ++ through the whole longList while consuming it wholy one
> element at a time! So when longList has n elements, you have (n+1) calls
> of ++, each returning after O(1) steps. The first n calls return a list
> with the ++ pushed down, and the last returns [5]. Summed together, that
> makes O(n) actual calls of ++ for one written by the programmer.
> 
>   Tillmann
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 
Lanny Ripple <[EMAIL PROTECTED]>
ScmDB / Cisco Systems, Inc.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re[2]: [Haskell-cafe] Damnit, we need a CPAN.

[Bulat Ziganshin]

Hello Neil,

Friday, May 30, 2008, 8:41:43 PM, you wrote:

>> Our reason to not commtting Grapefruit to Hackage so far was that this would
>> mean making an official release and we thought that Grapefruit is not yet
>> ready for this.

> Release it on hackage. Releasing to hacking means other people might
> find it useful - not that it is ready for production use.

once i've gathered stats about projects released on RubyForge.
"0.2" was the most popular version number there :))


-- 
Best regards,
 Bulatmailto:[EMAIL PROTECTED]

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Roberto Zunino]

Robin Green wrote:
> I have been thinking about to what extent you could cleanly do I/O
> without explicit use of the I/O monad, and without uniqueness types

Here's a way to see I/O as a pure functional data structure. To keep
things simple, we model only Char I/O:

data Program
  = Quit
  | Output Char Program
  | Input (Char -> Program)
  -- ... add here other I/O primitives if you want

-- Example:
cat :: Program
cat = Input (\c -> Output c cat)

-- Trivial mapping into the IO monad
runProgram :: Program -> IO ()
runProgram Quit = return ()
runProgram (Output c p) = putChar c >> runProgram p
runProgram (Input k)= getChar >>= runProgram . k

Another approach could be to use lazy I/O, à la interact. However, I am
uncomfortable with lazy I/O.

See also IOSpec, a nice functional model of the IO monad:

  http://www.cs.nott.ac.uk/~wss/repos/IOSpec/

Regards,
Zun.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Damnit, we need a CPAN.

[Neil Mitchell]

Hi

> Our reason to not commtting Grapefruit to Hackage so far was that this would
> mean making an official release and we thought that Grapefruit is not yet
> ready for this.  However, I might be wrong in the sense that also despite its
> current deficiencies, Grapefruit should be available from Hackage.  What do
> you think?

Release it on hackage. Releasing to hacking means other people might
find it useful - not that it is ready for production use. I think
other people on this thread have already said they want it, so a
hackage release is the way to go.

I sometimes release to hackage with no accouncement, just to make it
easier for users to use certain packages. For example, I doubt anyone
has heard of the homeomorphic package, but I have released it to
hackage.

Thanks

Neil
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Damnit, we need a CPAN.

[Wolfgang Jeltsch]

Am Donnerstag, 29. Mai 2008 17:47 schrieb Neil Mitchell:
> […]

> > grapefruit authors that commit to hackage
>
> Or someone to help show the grapefruit authors the light. I helped put
> smallcheck on hackage, others have done other packages. Perhaps you
> could do grapefruit?

What do you mean with showing us the light?  It’s not that I wouldn’t know how 
to do releases on Hackage.  I’ve already did this for the lax package.  It’s 
that we didn’t want to release yet because of Grapefruit’s inmaturity.

Anyway, thanks for motivating people to help. :-) 

> […]

Best wishes,
Wolfgang
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Damnit, we need a CPAN.

[Wolfgang Jeltsch]

Am Donnerstag, 29. Mai 2008 17:38 schrieb Achim Schneider:
> […]

> Rationale: We need […] grapefruit authors that commit to hackage

Our reason to not commtting Grapefruit to Hackage so far was that this would 
mean making an official release and we thought that Grapefruit is not yet 
ready for this.  However, I might be wrong in the sense that also despite its 
current deficiencies, Grapefruit should be available from Hackage.  What do 
you think?

By the way, it’s nice to hear that there are people which are really 
interested in trying Grapefruit out.  It still makes me wonder at times that 
I’ve made something that other people find really useful.  (Of course, I’ve 
not done Grapefruit alone but Matthias Reisner has also done a notable amount 
of work.)  So I would really like to get feedback concerning peoples 
impressions about Grapefruit.  Seeing interest in Grapefruit might give me 
more motivation for the work on it and therefore speed up its development.

> […]

> Anyway, three hours after wanting to try it out, grapefruit is up and
> running, and I did not even have to install its dependencies by hand. It
> seems like grapefruit could benefit from nestable cabal packages,
> though: It has one big script that installs many packages. You could
> also call them dependencies.

You could create a basically empty package named “grapefruit” which just 
depends on all Grapefruit packages.  Debian uses this concept for its 
packages.

> […]

Best wishes,
Wolfgang
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Seen on HCAR: CoreErlang library

[Dimitry Golubovsky]

Hi,

I have just spotted the item 5.4.3 on the recently issued HCAR:

CoreErlang is a Haskell library which consists of a parser and a
pretty-printer for the intermediate language used by Erlang.

There is no e-mail of the developer (Henrique Ferreiro Garcia) shown
on the report, so I am posting this on the mailing list.

What is the current status of this Core Erlang library? I might be
interested to use some parts of it in the Haskell to Erlang converter
that I am currently experimenting with.

Please contact me at golubovsky at gmail dot com.

Thank you.

-- 
Dimitry Golubovsky

Anywhere on the Web
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Jake Mcarthur]

On May 30, 2008, at 9:09 AM, Robin Green wrote:

eventMain :: (Event, SystemState AppState) -> (Command, SystemState  
AppState)


The first thing I would do with this type is probably wrap it up in a  
State monad so I don't have to keep track of the SystemState AppState  
stuff myself, which completely defeats the purpose. I don't think this  
really makes anything simpler at all.


Also see FRP for a perhaps more practical way of approaching IO as  
event streams.


- Jake___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Bryan O'Sullivan]

Ketil Malde wrote:

> I guess this is where I don't follow: why would you need more short
> strings for Unicode text than for ASCII or 8-bit latin text?

Because ByteString is optimised for dealing with big blobs of binary
data, its performance when you split a big ByteString into a pile of
words is quite poor.  Also, people use ByteStrings for dealing with text
mostly because their native character sets let them get away with it,
not because it's an intrinsically good idea.

http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Wolfgang Jeltsch]

Am Freitag, 30. Mai 2008 16:09 schrieb Robin Green:
> […]

> I'm primarily interested in embedded system and desktop UIs,

Than you should take a look at .

> […]

Best wishes,
Wolfgang
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] So how do people pronounce 'cabal' around here?

[Dan Piponi]

On Thu, May 29, 2008 at 8:58 PM, Jonathan Cast
<[EMAIL PROTECTED]> wrote:
> It's not French

'tis so! Two dictionaries I've now checked say it entered English from
Hebrew via French 'cabale'. But that has to be the last I say on this
as it's now well off topic.
--
Dan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Robin Green]

On Fri, 30 May 2008 15:23:46 +0100
Andrew Butterfield <[EMAIL PROTECTED]> wrote:

> Robin Green wrote:
> > I have been thinking about to what extent you could cleanly do I/O
> > without explicit use of the I/O monad, and without uniqueness types
> > (which are the main alternative to monads in pure functional
> > programming, and are used in the Concurrent Clean programming
> > language).
> >
> > Suppose you have a main event handler function, like this:
> >
> > eventMain :: (Event, SystemState AppState) -> (Command, SystemState
> > AppState)
> >
> > This function could be called over and over in an event loop, until
> > an EndProgram command was received, and the event loop would itself
> > do all the actual I/O (the SystemStates are only in-memory
> > representations of some part of the system state, plus the
> > application's own state). Things like disk I/O could be done with
> > commands which generate events when complete. Interprocess
> > communication could be done in the same way.
> >
> > Then eventMain, and everything called by it, would be
> > referentially-transparent, and yet non-monadic. You could of course
> > build higher-level stuff on top of that.
> >   
> Given the above, without uniqueness typing, and because there is
> clearly no monad,
> I could write
> 
> breakMain
>  :: (Event,Event,SystemState AppState)
>   -> ((Command,SystemState AppState),(Command,SystemState AppState))
> breakMain (e1,e2,sys) = ( eventMain (e1,sys) , eventMain (e2,sys) )
> 
> Now what happens? Do we get two copies of SystemState ?
> 
> Simpler still, I can write  (sys,eventMain e sys) -- what happens
> here? I have references to both before- and after- state.

Yes, you do - but they're only in-memory representations. Sorry, I
didn't fully explain what I meant. Two points:

1. The SystemState record only contains in-memory representations of
*some* parts of the system state - e.g. on an embedded system they could
be the on/off status of the LEDs, motor speeds, the state of the toggle
switches, which buttons are currently being pressed, etc. It would be
infeasible to record the entire state of, say, an attached 120GB hard
drive - and even less feasible to record the state of the external
environment - so only some parts of the system would be covered by this
data structure.

2. It's the event loop's job to do any necessary I/O to update the
*actual* system state to match the SystemState returned by eventMain
(ignoring any changes which are impossible, e.g. if the program tries
to say a toggle switch is on when it isn't). As I said, only in the
event loop is any I/O actually performed.

So when you evaluate breakMain or whatever, nothing happens - it's
just manipulating representations. You can only return one SystemState
from eventMain, and that is used to update the real system state - so
there's no paradox.
-- 
Robin
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: Damnit, we need a CPAN.

[Chaddaï Fouché]

2008/5/30 Achim Schneider <[EMAIL PROTECTED]>:
> I already was pleasantly surprised when discovering cabal-install, I
> think it deserves some more prominence, or even integration into cabal
> itself, to make everyone aware of the fact that there's such a thing as
> automatic installation and tempt people to make it work.

I completely agree, cabal-install is very nice, and should be more widely known.

> CPAN, of course, makes its life a lot easier by not caring about
> outside dependencies at all: You can install GTK bindings without
> having GTK installed... which of course does not work with Haskell, as
> things must be linked properly.

Not true : GTK bindings have a C part which needs to be properly
linked as well, you can't install them without GTK on your computer.
On the other hand, CPAN and the make-like tools in Perl are much more
mature and have more functionality than Cabal now (and they're a bit
of a mess too...) and there is often a external dependancies
downloader and installer integrated in packages.
Another truly important difference between CPAN and cabal-install is
the importance of the testing suite, all CPAN tools are geared so that
by default nothing is installed if it doesn't pass its test and
there's always a good number of tests. (So even when external
dependancies don't prevent the module from being build, it won't
install without forcing it)

-- 
Jedaï
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Andrew Butterfield]

Robin Green wrote:

I have been thinking about to what extent you could cleanly do I/O
without explicit use of the I/O monad, and without uniqueness types
(which are the main alternative to monads in pure functional
programming, and are used in the Concurrent Clean programming language).

Suppose you have a main event handler function, like this:

eventMain :: (Event, SystemState AppState) -> (Command, SystemState
AppState)

This function could be called over and over in an event loop, until an
EndProgram command was received, and the event loop would itself do all
the actual I/O (the SystemStates are only in-memory representations of
some part of the system state, plus the application's own state). Things
like disk I/O could be done with commands which generate events when
complete. Interprocess communication could be done in the same way.

Then eventMain, and everything called by it, would be
referentially-transparent, and yet non-monadic. You could of course
build higher-level stuff on top of that.
  
Given the above, without uniqueness typing, and because there is clearly 
no monad,

I could write

breakMain
:: (Event,Event,SystemState AppState)
 -> ((Command,SystemState AppState),(Command,SystemState AppState))
breakMain (e1,e2,sys) = ( eventMain (e1,sys) , eventMain (e2,sys) )

Now what happens? Do we get two copies of SystemState ?

Simpler still, I can write  (sys,eventMain e sys) -- what happens here?
I have references to both before- and after- state.

It is this probelm with copying the un-copiable (external I/O state),
that requires pure functional languages to outlaw such programs,
either via uniqueness typing, or via a monad interface that completely
hides any direct reference to the underlying state and which
then sequences the application of state transformers.
  



--

Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204
Foundations and Methods Research Group Director.
School of Computer Science and Statistics,
Room F.13, O'Reilly Institute, Trinity College, University of Dublin
   http://www.cs.tcd.ie/Andrew.Butterfield/


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I/O without monads, using an event loop

[Edsko de Vries]

On Fri, May 30, 2008 at 03:09:37PM +0100, Robin Green wrote:
> I have been thinking about to what extent you could cleanly do I/O
> without explicit use of the I/O monad, and without uniqueness types
> (which are the main alternative to monads in pure functional
> programming, and are used in the Concurrent Clean programming language).
> 
> Suppose you have a main event handler function, like this:
> 
> eventMain :: (Event, SystemState AppState) -> (Command, SystemState
> AppState)
> 
> This function could be called over and over in an event loop, until an
> EndProgram command was received, and the event loop would itself do all
> the actual I/O (the SystemStates are only in-memory representations of
> some part of the system state, plus the application's own state). Things
> like disk I/O could be done with commands which generate events when
> complete. Interprocess communication could be done in the same way.
> 
> Then eventMain, and everything called by it, would be
> referentially-transparent, and yet non-monadic. You could of course
> build higher-level stuff on top of that.
> 
> On the other hand, it's quite stateful, because anything you need to
> remember between events need to be recorded, either in the SystemState
> or externally (e.g. in a file). I suppose this is the most important
> disadvantage?
> 
> Is there any published work or code using this approach, or something
> like it, in a pure functional language? I'm primarily interested in
> embedded system and desktop UIs, rather than say web-based systems,
> although both would be interesting.

Yeah, check the History of Haskell paper, in particular Section 7.

Edsko
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Default definitions for associated type synonyms

[Dreixel]

Hello,

Does anyone know if it is possible to specify a default definition for an
associated type synonym? When I tried:

class A a where
>   type B a = a
>

GHC (version 6.9.20080309) told me: "Type declaration in a class must be a
kind signature or synonym default". However, when I look at the parser I see
no way to specify such synonym default. Is this possible?



Thanks,
Zé Pedro
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] I/O without monads, using an event loop

[Robin Green]

I have been thinking about to what extent you could cleanly do I/O
without explicit use of the I/O monad, and without uniqueness types
(which are the main alternative to monads in pure functional
programming, and are used in the Concurrent Clean programming language).

Suppose you have a main event handler function, like this:

eventMain :: (Event, SystemState AppState) -> (Command, SystemState
AppState)

This function could be called over and over in an event loop, until an
EndProgram command was received, and the event loop would itself do all
the actual I/O (the SystemStates are only in-memory representations of
some part of the system state, plus the application's own state). Things
like disk I/O could be done with commands which generate events when
complete. Interprocess communication could be done in the same way.

Then eventMain, and everything called by it, would be
referentially-transparent, and yet non-monadic. You could of course
build higher-level stuff on top of that.

On the other hand, it's quite stateful, because anything you need to
remember between events need to be recorded, either in the SystemState
or externally (e.g. in a file). I suppose this is the most important
disadvantage?

Is there any published work or code using this approach, or something
like it, in a pure functional language? I'm primarily interested in
embedded system and desktop UIs, rather than say web-based systems,
although both would be interesting.

-- 
Robin
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Ketil Malde]

"Johan Tibell" <[EMAIL PROTECTED]> writes:

> Lazy I/O comes with a penalty in terms of correctness! 

Is there a page describing this in more detail?  I believe my programs
to be correct, but would like to know if there are additional
pitfalls, beyond hClosing a handle with outstanding (unevaluated)
reads. 

> Lazy I/O is kinda, maybe usable for small scripts that reads a file
> or two and spits out a result but for servers it doesn't work at
> all.

So don't use it for servers, then?

> Here are two possible interfaces for safe I/O. One isstream based
> one with explicit close and the other fold based one (i.e. inversion
> of control):

Say I have two files with variable-size records, that need to be
merged.  In other words, I can do something like:

  do
xs <- readFile "X"
ys <- readFile "Y"
return $ zipWith combine (parseX xs) (parseY ys)

Clearly in the "small script" category and not "servers", but is it
still unsafe?

>> -- Stream based I/O.
>> -- Left fold/callback based I/O.

Perhaps I don't quite understand the concepts, but I don't see how to
implement the example as elegantly and simply with these approaches?

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Damnit, we need a CPAN.

[Achim Schneider]

Duncan Coutts <[EMAIL PROTECTED]> wrote:

> So I fully appreciate this packaging stuff is sometimes frustrating. I
> hope you appreciate that it is actually improving.
>
I already was pleasantly surprised when discovering cabal-install, I
think it deserves some more prominence, or even integration into cabal
itself, to make everyone aware of the fact that there's such a thing as
automatic installation and tempt people to make it work.

CPAN, of course, makes its life a lot easier by not caring about
outside dependencies at all: You can install GTK bindings without
having GTK installed... which of course does not work with Haskell, as
things must be linked properly.

-- 
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited. 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] type-level integers using type families

[Roberto Zunino]

Manuel M T Chakravarty wrote:
> Peter Gavin:
>> will work if the non-taken branch can't be unified with anything.  Is
>> this planned? Is it even feasible?
> 
> I don't think i entirely understand the question.

Maybe he wants, given

  cond :: Cond x y z => x -> y -> z
  tt :: True
  true_exp  :: a
  false_exp :: <<>>

that

  cond tt true_exp false_exp :: a

That is the type of false_exp is "lazily inferred", so that type errors
do not make inference fail if they show up in an unneeded place.

If we had subtyping, typing that as Top would suffice, I believe.

Zun.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Isaac Dupree]

it makes me wonder: can we support concatenation with sharing (e.g. the 
"rope" data structure)

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Johan Tibell]

On Fri, May 30, 2008 at 12:11 PM, Duncan Coutts
<[EMAIL PROTECTED]> wrote:
> On Fri, 2008-05-30 at 10:38 +0200, Ketil Malde wrote:
>> "Johan Tibell" <[EMAIL PROTECTED]> writes:
>> > But ByteStrings are neither ASCII nor 8-bit Latin text!
>>   [...]
>> > The intent of the not-yet-existing Unicode string is to represent
>> > text not bytes.
>>
>> Right, so this will replace the .Char8 modules as well?
>
> No, there is still a use-case for that, namely all these network
> protocols and file formats that mix binary and ASCII data.

After implementing an HTTP parser using ByteString in my web server I
can say that the only thing you need from the .Char8 module is `pack'
to be able to write byte literals. Matching bytes is better done using
something like a `ByteSet' rather than the .Char8 functions as it
gives better performance.

-- Johan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] is there some book about haskell and data struct and alg?

[Benjamin L. Russell]

Actually, the link now points to the following URL (updated by John Melesky):

http://www.eecs.usma.edu/webs/people/okasaki/pfds-haskell.tar.gz

instead of the following URL (set by Henk-Jan van Tuyl):

http://web.archive.org/web/2818044004/http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz

I just tested both, and they both seem to work.  Perhaps both should be listed, 
or should we agree on just one?

Benjamin L. Russell

--- On Thu, 5/29/08, Henk-Jan van Tuyl <[EMAIL PROTECTED]> wrote:

> From: Henk-Jan van Tuyl <[EMAIL PROTECTED]>
> Subject: Re: [Haskell-cafe] is there some book about haskell and data struct 
> and alg?
> To: "Benjamin L. Russell" <[EMAIL PROTECTED]>, "haskell-cafe@haskell.org" 
> 
> Date: Thursday, May 29, 2008, 5:56 PM
> On Thu, 29 May 2008 05:11:54 +0200, Benjamin L. Russell  
> <[EMAIL PROTECTED]> wrote:
> 
> > Although all the source code for the pdf version  
> > (http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf) of
> "Purely Functional  
> > Data Structures" is provided in Standard ML, not
> Haskell, I found a  
> > broken link to the supposedly equivalent Haskell
> source code on "Books -  
> > HaskellWiki"
> (http://haskell.org/haskellwiki/Books):
> >
> > Haskell source code for the book:
> > http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz
> >
> > Clicking on this link results in the following error:
> [...]
> >
> > Without the equivalent Haskell source code, the code
> must be manually  
> > translated from Standard ML into Haskell.  Does
> anybody know why the  
> > link is broken, when it may be fixed, and from where
> the Haskell source  
> > code can be currently obtained?
> 
> It appears that http://www.cs.columbia.edu/~cdo/ does not
> exist anymore;  
> probably because the owner does not study/work at the
> university anymore.  
> I fixed the link, it now points to the copy stored in the
> Wayback Machine  
> ( http://web.archive.org/ ).
> The new link is:
>   
> http://web.archive.org/web/2818044004/http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz
> 
> -- 
> Met vriendelijke groet,
> Henk-Jan van Tuyl
> 
> 
> --
> http://functor.bamikanarie.com
> http://Van.Tuyl.eu/
> --
> 
> 
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Duncan Coutts]

On Fri, 2008-05-30 at 10:38 +0200, Ketil Malde wrote:
> "Johan Tibell" <[EMAIL PROTECTED]> writes:
> 
> >> I guess this is where I don't follow: why would you need more short
> >> strings for Unicode text than for ASCII or 8-bit latin text?
> 
> > But ByteStrings are neither ASCII nor 8-bit Latin text! 
>   [...] 
> > The intent of the not-yet-existing Unicode string is to represent
> > text not bytes. 
> 
> Right, so this will replace the .Char8 modules as well? 

No, there is still a use-case for that, namely all these network
protocols and file formats that mix binary and ASCII data.

The only bad thing about the .Char8 modules is how people have picked
them up to represent text exclusively which is a step back from [Char]
in terms of Unicode stuff.

> What confused me was my misunderstanding Duncan to mean that Unicode
> text would somehow imply shorter strings than non-Unicode (i.e. 8-bit)
> text.

ByteString is already not a good choice for short ASCII text.

Duncan

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] test driving cabal install... cabal install and normal install (runghc Setup) don't mix... two package.conf files...

[Duncan Coutts]

On Thu, 2008-05-29 at 20:12 -0700, Philip Neustrom wrote:

> I'm having issues trying to get cabal-install (latest darcs)
> installed, as well.  I'm seeing the message:
> 
> Hackage/Types.hs:19:29:
> Module `Distribution.Version' does not export `Dependency'
> 
> which was mentioned on this list earlier.  Updating to the latest
> darcs Cabal doesn't do the trick, it seems:
> 
> $ ghc-pkg list
> /usr/local/lib/ghc-6.8.2/package.conf:
> Cabal-1.3.10, Cabal-1.5.2, ...
> 
> I grabbed that 1.3.10 as a tarball snapshot.

If you used the tarball of Cabal then you'd want the corresponding
tarball of cabal-install that was released at the same time. Otherwise
the darcs version of one requires the darcs version of the other.

>   The darcs cabal installs Cabal-1.5.2, and it seemed that the darcs
> cabal-install wanted >= 1.3.11 && < 1.5, so I've no idea what to do
> here :)

I'll be making the 1.4 release from this branch:
http://darcs.haskell.org/cabal-branches/cabal-1.4/

which is currently at version 1.3.11 since we've not hit 1.4 yet.

Duncan

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Johan Tibell]

Hi!

On Fri, May 30, 2008 at 10:38 AM, Ketil Malde <[EMAIL PROTECTED]> wrote:
> "Johan Tibell" <[EMAIL PROTECTED]> writes:
>> The intent of the not-yet-existing Unicode string is to represent
>> text not bytes.
>
> Right, so this will replace the .Char8 modules as well?  What confused
> me was my misunderstanding Duncan to mean that Unicode text would
> somehow imply shorter strings than non-Unicode (i.e. 8-bit) text.

Yes.

>> To give just one example, short (Unicode) strings are common as keys
>> in associative data structures like maps
>
> I guess typically, you'd break things down to words, so strings of
> lenght 4-10 or so.  BS uses three words and LBS four (IIRC), so the
> cost of sharing typically outweighs the benefit.

I'm not sure if you would have much sharing in a map as the keys will be unique.

>> Can I also here insert a plea for keeping lazy I/O out of the new
>> Unicode module?
>
> I use ByteString.Lazy almost exclusively.  I realize it there's a
> penalty in time and space, but the ability to write applications that
> stream over multi-Gb files is essential.

Lazy I/O comes with a penalty in terms of correctness! Pretending that
I/O and the underlying resource allocations (e.g. file handles) aren't
observable is bad. Lazy I/O is kinda, maybe usable for small scripts
that reads a file or two an spits out a result but for servers it
doesn't work at all. Lazy I/O requires unsafe* functions and is
therefore, unsafe. The finalizers required can be arbitrary complex
depending on what kind of resources need to be allocated. The simple
case is a file handle but there's no reason we might need sockets,
locks, etc to create the lazy ByteString. Here are two possible
interfaces for safe I/O. One isstream based one with explicit close
and the other fold based one (i.e. inversion of control):

> import qualified Data.ByteString as S
>
> -- Stream based I/O.
> class InputStream s where
>   read :: s -> IO Word8
>   readN :: s -> Int -> IO S.ByteString  -- efficient block reads
>   close :: s -> IO ()
>
> openBinaryFile :: InputStream s => FilePath -> IO s

or a left fold over the file's content. The 'foldBytes' function can
close the file at EOF.

> -- Left fold/callback based I/O.
> foldBytes :: FilePath -> (seed -> Word8 -> Either seed seed) -> seed -> IO 
> seed
> -- Efficient block reads.
> foldChunks :: FilePath -> (seed -> S.ByteString -> Either seed seed) -> seed 
> -> IO seed

on top of this you might want monadic versions of the above two
functions. The case for a Unicode type are analogous.

> Of course, these applications couldn't care less about Unicode, so
> perhaps the usage is different.

The issue of lazy I/O is orthogonal to ByteString vs Unicode(String).

Cheers,

Johan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] zlib, missing zlib.h

[Tony Morris]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

apt-get install zlib1g-dev

Tony Morris
http://tmorris.net/

Real-world problems are simply degenerate cases of pure mathematical
problems.



Thomas Hartman wrote:
> Tried to install
> 
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/zlib
> 
> which is required for
> 
> http://darcs.haskell.org/cabal-branches/cabal-1.4
> 
> which is required for cabal-install.
> 
> Got the following error. apt-get installed zlibc on a stab in the
> dark, but same result. advice?
> 
> [EMAIL 
> PROTECTED]:~/haskellInstalls/smallInstalls/cabal-install/zlib-0.4.0.4>runghc
> Setup.hs configure
> Configuring zlib-0.4.0.4...
> 
> [EMAIL 
> PROTECTED]:~/haskellInstalls/smallInstalls/cabal-install/zlib-0.4.0.4>runghc
> Setup.hs build &>out
> 
> [EMAIL 
> PROTECTED]:~/haskellInstalls/smallInstalls/cabal-install/zlib-0.4.0.4>head
> out
> Preprocessing library zlib-0.4.0.4...
> 
> Stream.hsc:74:18:  error: zlib.h: No such file or directory
> Stream.hsc: In function 'main':
> 
> Stream.hsc:254:0:
>  error: 'z_stream' undeclared (first use in this function)
> 
> Stream.hsc:254:0:
>  error: (Each undeclared identifier is reported only once
> [EMAIL PROTECTED]:~/haskellInstalls/smallInstalls/cabal-install/zlib-0.4.0.4>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 
> 
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFIP8GgmnpgrYe6r60RAjGGAKDCpiIE9IGv5Madf2jMhEZCDuuEhgCdGljK
ztH9XwTczFX7ABBrh3TuT8I=
=jR/y
-END PGP SIGNATURE-
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Ketil Malde]

"Johan Tibell" <[EMAIL PROTECTED]> writes:

>> I guess this is where I don't follow: why would you need more short
>> strings for Unicode text than for ASCII or 8-bit latin text?

> But ByteStrings are neither ASCII nor 8-bit Latin text! 
  [...] 
> The intent of the not-yet-existing Unicode string is to represent
> text not bytes. 

Right, so this will replace the .Char8 modules as well?  What confused
me was my misunderstanding Duncan to mean that Unicode text would
somehow imply shorter strings than non-Unicode (i.e. 8-bit) text.

> To give just one example, short (Unicode) strings are common as keys
> in associative data structures like maps

I guess typically, you'd break things down to words, so strings of
lenght 4-10 or so.  BS uses three words and LBS four (IIRC), so the
cost of sharing typically outweighs the benefit.

> Can I also here insert a plea for keeping lazy I/O out of the new
> Unicode module?

I use ByteString.Lazy almost exclusively.  I realize it there's a
penalty in time and space, but the ability to write applications that
stream over multi-Gb files is essential.

Of course, these applications couldn't care less about Unicode, so
perhaps the usage is different.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: type-level integers using type families

[Benedikt Huber]

Peter Gavin schrieb:

Has anyone else tried implementing type-level integers using type families?

I tried using a couple of other type level arithmetic libraries 
(including type-level on Hackage) and they felt a bit clumsy to use.  I 
started looking at type families and realized I could pretty much build 
an entire Scheme-like language based on them.


In short, I've got addition, subtraction, & multiplication working after 
just a days worth of hacking. I'm going to post the darcs archive 
sometime, sooner if anyone's interested.


I really like the type-families based approach to this, it's a lot 
easier to understand, and you can think about things functionally 
instead of relationally.  (Switching back and forth between Prolog-ish 
thinking and Haskell gets old quick.) Plus you can do type arithmetic 
directly in place, instead of using type classes everywhere.


I tried to rewrite Alfonso Acosta's type-level library (the one on 
hackage) using type-families too, because, right, they are much nicer to 
use than MPTCs.


It is a straigtforward translation, I've uploaded it to

http://code.haskell.org/~bhuber/type-level-tf-0.2.1.tar.gz

now (relevant files: src/Data/TypeLevel/{Bool.hs,Num/Ops.hs}).

I've also added a type-level ackermann to torture ghc a little bit ;),
but left out logarithms. Plus, I did very little testing.


One thing that I'd like to be able to do is lazy unification on type instances, 
so that things like

data True
data False

type family Cond x y z
type instance Cond True y z = y
type instance Cond False y z = z 


I'm not sure if this is what you had in mind, but I also found that e.g.

> type instance Mod x y = Cond (y :>: x) x  (Mod (Sub x y) y)

won't terminate, as

> Mod D0 D1 ==> Cond True D0 (Mod (Sub D0 D1) D0) ==> 

rather than

> Mod D0 D1 ==> Cond True D0 ? ==> D0

For Mod, I used the following (usual) encoding:

> type family Mod' x y x_gt_y
> type instance Mod' x y False = x
> type instance Mod' x y True  = Mod' (Sub x y) y ((Sub x y) :>=: y)
> type family Mod x y
> type instance Mod x y = Mod' x y (x :>=: y)

There are few other things you cannot do with type families, and some 
for which you need type classes anyway (Alfonso pointed me to 
http://www.haskell.org/pipermail/haskell-cafe/2008-February/039489.html 
). Here's what I found:



1) One cannot define type equality (unless total type families become
available), i.e. use the overlapping instances trick:

instance Eq e e  True
instance Eq e e' False


Consequently, all type-level functions which depend on type equality
(see HList) need to be encoded using type classes.

2) One cannot use superclass contexts to derive instances e.g. to define

instance Succ (s,s') =>  Pred (s',s)


In constrast, when using MPTC + FD, one can establish more than one TL 
function in one definition


> class Succ x x' | x -> x', x' -> x

3) Not sure if this is a problem in general, but I think you cannot 
restrict the set of type family instances easily.


E.g., if you have an instance

> type instance Mod10 (x :* D0) = D0

then you also have

> Mod10 (FooBar :* D0) ~ D0

What would be nice is something like

> type instance (IsPos x) => Mod10 (x :* D0) = D0

though

> type family AssertThen b x
> type instance AssertThen True x = x
> type instance Mod10 (x :* D0) = AssertThen (IsPos x) D0

seems to work as well.

4) Not really a limitation, but if you want to use instance methods of
Nat or Bool (e.g. toBool) on the callee site, you have to provide
context that the type level functions are closed w.r.t. to the type class:


test_1a :: forall a b b1 b2 b3.
  (b1 ~ And a b,
   b2 ~ Not (Or a b),
   b3 ~ Or b1 b2,
   Bool b3) => a -> b -> Prelude.Bool
test_1a a b = toBool (undefined :: b3)


Actually, I think the 'a ~ b' syntax is very nice.

I'm really looking forward to type families.

best regards,

benedikt
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] modelling C in Haskell ..

[Jonathan Cast]

On 30 May 2008, at 12:29 AM, Galchin, Vasili wrote:


compactness in writing and also namespace pollution .. ;^)


I know what the advantages of C's notation are.  But getting the best  
notation out of Haskell generally doesn't happen by trying to make  
your code look like C.


So the general answer to questions of the form `C can do x; can  
Haskell' is `No'.  Don't do it like in C.  It won't be idiomatic, it  
won't be elegant, and neither of us will like the results.   
Understand the features of Haskell that make your program compact,  
point-free (how Haskell handles namespace pollution), and elegant and  
use those.  This will require a different factoring of your program  
vs. C.  Sorry, but that's life.


jcc

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Johan Tibell]

On Fri, May 30, 2008 at 9:00 AM, Ketil Malde <[EMAIL PROTECTED]> wrote:
> Duncan Coutts <[EMAIL PROTECTED]> writes:
>> The reason we do not want to re-use ByteString as the underlying
>> representation is because they're not good for short strings and we
>> expect that for Unicode text (more than arbitrary blobs of binary data)
>> people will want efficient short strings.
>
> I guess this is where I don't follow: why would you need more short
> strings for Unicode text than for ASCII or 8-bit latin text?

But ByteStrings are neither ASCII nor 8-bit Latin text! The latter
might be internally represented using an 8-bit encoding but saying
that they are the same would be to confuse representation with
intended use. The use case for ByteString is representing a sequence
of bytes used in e.g. fast binary socket and file I/O. The intent of
the not-yet-existing Unicode string is to represent text not bytes.
These are different use cases so having to make different trade-offs
shouldn't come as a surprise. To give just one example, short
(Unicode) strings are common as keys in associative data structures
like maps where fast allocation, small memory footprint and fast
comparison is important. That being said it's entirely possible that I
didn't get your point.

Can I also here insert a plea for keeping lazy I/O out of the new
Unicode module?

-- Johan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re[2]: [Haskell-cafe] Copying Arrays

[Bulat Ziganshin]

Hello Ketil,

Friday, May 30, 2008, 11:00:10 AM, you wrote:

> I guess this is where I don't follow: why would you need more short
> strings for Unicode text than for ASCII or 8-bit latin text?

BS package require too much memory for storing short strings.
alternative package that minimizes memory would be useful


-- 
Best regards,
 Bulatmailto:[EMAIL PROTECTED]

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] ANNOUNCE: Haskell Communities and Activities Report (14th ed., May 2008)

[Janis Voigtlaender]

On behalf of the many, many contributors, we are pleased to announce
that the

  Haskell Communities and Activities Report
(14th edition, May 2008)

 http://www.haskell.org/communities/

is now available from the Haskell Communities home page in PDF and
HTML formats.

Many thanks go to all the people that contributed to this report,
both directly, by sending in descriptions, and indirectly, by doing
all the interesting things that are reported. We hope you will find
it as interesting a read as we did.

If you haven't encountered the Haskell Communities and Activities
Reports before, you may like to know that the first of these reports
was published in November 2001. Their goal is to improve the
communication between the increasingly diverse groups, projects and
individuals working on, with, or inspired by Haskell. The idea behind
these reports is simple:

Every six months, a call goes out to all of you enjoying Haskell to
contribute brief summaries of your own area of work. Many of you
respond (eagerly, unprompted, and well in time for the actual
deadline ;) ) to the call. The editor collects all the contributions
into a single report and feeds that back to the community.

When we try for the next update, six months from now, you might want
to report on your own work, project, research area or group as well.
So, please put the following into your diaries now:


   End of October 2008:
target deadline for contributions to the
November 2008 edition of the HC&A Report


Unfortunately, many Haskellers working on interesting projects are so
busy with their work that they seem to have lost the time to follow
the Haskell related mailing lists and newsgroups, and have trouble even
finding time to report on their work. If you are a member, user or
friend of a project so burdened, please find someone willing to make
time to report and ask them to `register' with the editor for a simple
e-mail reminder in the middle of November (you could point us to them as
well, and we can then politely ask if they want to contribute, but it
might work better if you do the initial asking). Of course, they will
still have to find the ten to fifteen minutes to draw up their report,
but maybe we can increase our coverage of all that is going on in the
community.

Feel free to circulate this announcement further in order to
reach people who might otherwise not see it. Enjoy!

Andres Loeh and Janis Voigtlaender


--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:[EMAIL PROTECTED]

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] modelling C in Haskell ..

[Galchin, Vasili]

compactness in writing and also namespace pollution .. ;^)

Vasili


On Fri, May 30, 2008 at 2:12 AM, Jonathan Cast <[EMAIL PROTECTED]>
wrote:

> On 29 May 2008, at 11:46 PM, Galchin, Vasili wrote:
>
>  Hello,
>>
>> I don't want to write kludgy Haskell code!
>>
>> typedef struct blah
>> {
>>   int val1;
>>
>>   union {
>>
>>   int  val2;
>>
>>   struct {
>>
>> int val3;
>>
>> int val4;
>>   }
>>   }
>> }C_type;
>>
>> question: in Haskell, can I embed definition of the "union" inside of the
>> C typedef, i.e. recursion definition? Or must I have a separate definition
>> for the "union" which I "instantiate" inside the Haskell "typedef", i.e.
>> Haskell "data"?
>>
>
> Assuming all of these are semantic, you can say
>
> newtype HS_type = HS_type (Int, Either Int (Int, Int))
>
> But you lose named fields.
>
> It's hard to give other advice without some idea of /why/ you want to do
> something like this.
>
> jcc
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] modelling C in Haskell ..

[Jonathan Cast]

On 29 May 2008, at 11:46 PM, Galchin, Vasili wrote:


Hello,

 I don't want to write kludgy Haskell code!

typedef struct blah
{
   int val1;

   union {

   int  val2;

   struct {

 int val3;

 int val4;
   }
   }
}C_type;

question: in Haskell, can I embed definition of the "union" inside  
of the C typedef, i.e. recursion definition? Or must I have a  
separate definition for the "union" which I "instantiate" inside  
the Haskell "typedef", i.e. Haskell "data"?


Assuming all of these are semantic, you can say

newtype HS_type = HS_type (Int, Either Int (Int, Int))

But you lose named fields.

It's hard to give other advice without some idea of /why/ you want to  
do something like this.


jcc

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Copying Arrays

[Ketil Malde]

Duncan Coutts <[EMAIL PROTECTED]> writes:

>>> Because I'm writing the Unicode-friendly ByteString =p

> He's designing a proper Unicode type along the lines of ByteString.

So - storing 22.5 bit code points instead of 8-bit quantities?  Or
storing whatever representation from the input, and providing a nice
interface on top?

>> Perhaps I'm not understanding.  Why wouldn't you use ByteString for I/O,

Like everybody else, my first reaction is to put a layer (like Char8)
on top of lazy bytestrings.  For variable-length encodings, you lose
direct indexing, but I think this is not very common, and if you need
it, you should convert to a fixed length encoding instead.  Since a BS
is basically a (pointer to array,offset,length) triple, it should be
relatively easy to ensure that you don't break a wide char between
chunks by adjusting the length (which doesn't have to match the
actual array length).

> The reason we do not want to re-use ByteString as the underlying
> representation is because they're not good for short strings and we
> expect that for Unicode text (more than arbitrary blobs of binary data)
> people will want efficient short strings.

I guess this is where I don't follow: why would you need more short
strings for Unicode text than for ASCII or 8-bit latin text?

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe