Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Looking for a datastructure (Ertugrul Soeylemez)
2. Re: FW: question (Roelof Wobben)
3. Re: Looking for a datastructure (Chadda? Fouch?)
4. Re: Looking for a datastructure (Kees Bleijenberg)
5. Re: Looking for a datastructure (David Place)
6. Re: Looking for a datastructure (David Place)
7. Re: Monads in javascript (Martin Drautzburg)
----------------------------------------------------------------------
Message: 1
Date: Fri, 15 Jul 2011 12:12:46 +0200
From: Ertugrul Soeylemez <[email protected]>
Subject: Re: [Haskell-beginners] Looking for a datastructure
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII
"Kees Bleijenberg" <[email protected]> wrote:
> My program uses a very long list of (index,count) items. Index and count are
> Int's.
> The program updates the count values a lot. Therefor it uses the index as a
> key to update the belonging count value.
> After updating, the program needs the (index,count) pair with the least
> count value in the list.
> What is an approriate (fast) datastructure? My first idea was to use a heap.
> Problem with the heap is that I can't update the count value by its index
> fast.
> Any ideas?
Try Data.IntMap and Data.Map. I think they have different asymptotics,
but they both do exactly what you want, so try both. Because of the
purity I would estimate the total query time to O(log n) and the total
update time to O((log n)^2).
Greets,
Ertugrul
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
------------------------------
Message: 2
Date: Fri, 15 Jul 2011 10:15:08 +0000
From: Roelof Wobben <[email protected]>
Subject: Re: [Haskell-beginners] FW: question
To: <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Oke,
Everyone thanks for the help.
Roelof
----------------------------------------
> Subject: Re: [Haskell-beginners] FW: question
> From: [email protected]
> Date: Thu, 14 Jul 2011 10:40:17 -0400
> CC: [email protected]
> To: [email protected]
>
> On Jul 14, 2011, at 10:20 AM, Roelof Wobben wrote:
>
> > The initial question was about the difference between what you call Latex
> > and Haskell symbols.
> >
> > I must say that this book explains things better then the other books I
> > tried.
>
> On the web page for that book, there are a number of code sample files to
> download. Maybe you could look there for some good concrete examples of
> syntax. Note that they are in Literary Programming Style.
>
>
> > http://www.cs.nott.ac.uk/~gmh/book.html
>
>
>
> ____________________
> David Place
> Owner, Panpipes Ho! LLC
> http://panpipesho.com
> [email protected]
>
>
>
------------------------------
Message: 3
Date: Fri, 15 Jul 2011 12:13:21 +0200
From: Chadda? Fouch? <[email protected]>
Subject: Re: [Haskell-beginners] Looking for a datastructure
To: Kees Bleijenberg <[email protected]>
Cc: [email protected]
Message-ID:
<CANfjZRZuG5YVqmbMiu6zrNpjK0mhk=QLyU56gke=ben3lgc...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Fri, Jul 15, 2011 at 11:42 AM, Kees Bleijenberg
<[email protected]> wrote:
> My program uses?a very long list of (index,count) items. Index and
> count?are?Int's.
> The program?updates the count values a lot. Therefor?it uses?the index as a
> key to?update the belonging count value.
> After updating, the program needs the (index,count) pair with the least
> count value in the list.
> What is an approriate (fast)?datastructure? My first idea was to use a heap.
> Problem?with the?heap is that I can't update the count value by its index
> fast.
> Any ideas?
Do you need to be able to "remove" the pair that has the least count cheaply ?
--
Jeda?
------------------------------
Message: 4
Date: Fri, 15 Jul 2011 14:30:11 +0200
From: "Kees Bleijenberg" <[email protected]>
Subject: Re: [Haskell-beginners] Looking for a datastructure
To: <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Jeda?,
On Fri, Jul 15, 2011 at 11:42 AM, Kees Bleijenberg
<[email protected]> wrote:
> My program uses?a very long list of (index,count) items. Index and
> count?are?Int's.
> The program?updates the count values a lot. Therefor?it uses?the index
> as a key to?update the belonging count value.
> After updating, the program needs the (index,count) pair with the
> least count value in the list.
> What is an approriate (fast)?datastructure? My first idea was to use a
heap.
> Problem?with the?heap is that I can't update the count value by its
> index fast.
> Any ideas?
Do you need to be able to "remove" the pair that has the least count cheaply
?
Yes, that would be nice. But as an alternative I can give give it a very,
very high count.
I need an index to access the elements (just like a map) and the map should
stay sorted on another 'field' then the key (or at least it should act as a
heap for that 'non-key field').
Kees
------------------------------
Message: 5
Date: Fri, 15 Jul 2011 10:29:50 -0400
From: David Place <[email protected]>
Subject: Re: [Haskell-beginners] Looking for a datastructure
To: "Kees Bleijenberg" <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Jul 15, 2011, at 8:30 AM, Kees Bleijenberg wrote:
> I need an index to access the elements (just like a map) and the map should
> stay sorted on another 'field' then the key (or at least it should act as a
> heap for that 'non-key field').
>
> Kees
Hi, Kees.
Have you looked into fingertrees? They give an enormously powerful way to
express incremental computations over trees with big O logarithmic complexity.
> http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
____________________
David Place
Owner, Panpipes Ho! LLC
http://panpipesho.com
[email protected]
------------------------------
Message: 6
Date: Fri, 15 Jul 2011 12:21:02 -0400
From: David Place <[email protected]>
Subject: Re: [Haskell-beginners] Looking for a datastructure
To: Kees Bleijenberg <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Jul 15, 2011, at 8:30 AM, Kees Bleijenberg wrote:
> need an index to access the elements (just like a map) and the map should
> stay sorted on another 'field' then the key (or at least it should act as a
> heap for that 'non-key field').
More on fingertrees. In fact, i think this module in the fingertree package
does exactly what you need.
> http://hackage.haskell.org/packages/archive/fingertree/0.0.1.0/doc/html/Data-PriorityQueue-FingerTree.html
____________________
David Place
Owner, Panpipes Ho! LLC
http://panpipesho.com
[email protected]
------------------------------
Message: 7
Date: Sat, 16 Jul 2011 10:16:52 +0200
From: Martin Drautzburg <[email protected]>
Subject: Re: [Haskell-beginners] Monads in javascript
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
Back to the question "why can't I get the intermediate results"
In Haskell I can do things like
f::Int->[Int]
f x = [x+1]
z :: [Int]
z = do
y1 <- [1,2,3]
y2 <- f y1
return (y1*y2)
i.e. I can access an intermediate result y1 and the end of the chain. When I
write this without do notation I get
z' = [1,2,3] >>= \y1->[y1+1] >>= \y2->return (y1*y2)
which of course works just as well. However I must not put parentheses around
the lambdas:
z' = [1,2,3] >>= (\y1->[y1+1]) >>= (\y2->return (y1*y2))
Not in scope: `y1'
However
z' = [1,2,3] >>= (\y1->[y1+1] >>= (\y2->return (y1*y2)))
works again, which misled me to believe that (>>=) associates to the right.
In javascript a lambda would look like this
f = function(y1) {return [y1+1]}
I cannot see how I could possible write a function (>>=) which chains such
lambdas such that I can still access the arguments outside the function
bodies. It is like there are always parentheses around the lambdas. Well there
actually are braces in javascript, but it can't be just the syntax.
So what is javascript missing? Is it because in haskell a lambda is just an
expression wheras in javascript it is something special?
--
Martin
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 37, Issue 29
*****************************************
