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. library for lattice data structure (James Toll)
2. Re: library for lattice data structure (Brent Yorgey)
3. Re: library for lattice data structure (Kim-Ee Yeoh)
4. Re: library for lattice data structure (James Toll)
5. Re: library for lattice data structure (James Toll)
6. Re: library for lattice data structure (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Tue, 11 Mar 2014 19:51:23 -0500
From: James Toll <[email protected]>
To: haskell-beginners <[email protected]>
Subject: [Haskell-beginners] library for lattice data structure
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
Hi,
I have a general question regarding data structures, maybe functional data
structures, in Haskell and I?m hoping for some advice. I would like to
implement the binomial option pricing model in Haskell.
https://en.wikipedia.org/wiki/Binomial_options_pricing_model
Given its lattice structure, I originally thought of trying a recursive
implementation, but because it?s recombining, the interior nodes would be
calculated twice. Although the implementation might be elegant, it doesn?t
seem inefficient. Therefore I?ve been searching through Hackage for a data
structure library that might lend itself to this problem. There are a ton of
libraries and as I don?t have any experience with them, I was hoping someone
could provide some advice to narrow the field.
Some of the packages I've found so far are:
lattices package
http://hackage.haskell.org/package/lattices
>From the name I thought this might be perfect, but the documentation is very
>terse and there doesn?t appear to be any other documentation so I?m not even
>sure how to get started with constructing a lattice with this package.
matrix package
https://hackage.haskell.org/package/matrix
This package seems fairly straightforward, and a matrix would work (it?s
probably what I would use in R), but it doesn?t seem ideal. There are other
more sophisticated packages with matrices like hmatrix and repa but they seem
like overkill unless this package is just slow.
vector package
https://hackage.haskell.org/package/vector
Vectors might also work for a data structure, but a matrix just seems like it
would be easier.
I thought this example implementation in Haskell was intriguing but it doesn?t
sound as though it?s very quick.
http://www.thulasidas.com/2009-03/a-new-kind-of-binomial-tree.htm
Any advice on an appropriate data structure in Haskell for the problem? The
solution doesn?t necessarily have to include a package.
Thanks
James
------------------------------
Message: 2
Date: Tue, 11 Mar 2014 21:40:47 -0400
From: Brent Yorgey <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] library for lattice data structure
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Hi James,
On Tue, Mar 11, 2014 at 07:51:23PM -0500, James Toll wrote:
> Hi,
>
> I have a general question regarding data structures, maybe functional data
> structures, in Haskell and I?m hoping for some advice. I would like to
> implement the binomial option pricing model in Haskell.
>
> https://en.wikipedia.org/wiki/Binomial_options_pricing_model
>
> Given its lattice structure, I originally thought of trying a
> recursive implementation, but because it?s recombining, the interior
> nodes would be calculated twice.
It's even worse than that---a naive implementation will end up doing
exponentially too much work. The interior nodes are recalculated much more
than just twice.
I once had a student who implemented exactly this, and did it in a
clever way---they constructed an actual binary tree data structure,
but using some "knot-tying" techniques
(http://www.haskell.org/haskellwiki/Tying_the_Knot) to result in all
the internal nodes actually being shared in memory. So it really was
a binary tree data structure but in memory it looked like a lattice.
> lattices package
> http://hackage.haskell.org/package/lattices
> From the name I thought this might be perfect, but the documentation is very
> terse and there doesn?t appear to be any other documentation so I?m not even
> sure how to get started with constructing a lattice with this package.
This package is actually about the mathematical abstraction of
lattices; it has nothing to do with data structures.
Matrices and vectors are definitely too low-level for this problem.
> I thought this example implementation in Haskell was intriguing but it
> doesn?t sound as though it?s very quick.
> http://www.thulasidas.com/2009-03/a-new-kind-of-binomial-tree.htm
You're right; this implementation has the exponential blowup problem.
However, it's actually possible to take this code and make some simple
modifications so that it runs quickly, by memoizing the function f.
One simple way to do that is to replace the function f with lookups
into an array---the trick is that you can construct the array
recursively, and thanks to laziness the entries in the array will
automatically be computed in the right order, so you don't have to
worry about that like you would in, say, R. For an example, see the
very last section (titled "Dynamic Programming") on this page:
http://www.cis.upenn.edu/~cis194/lectures/06-laziness.html
-Brent
------------------------------
Message: 3
Date: Wed, 12 Mar 2014 09:57:53 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] library for lattice data structure
Message-ID:
<CAPY+ZdQyV26pChikaHAspEui1=qYPJqLEkaM2nqiSC6u-U=q...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Mar 12, 2014 at 7:51 AM, James Toll <[email protected]> wrote:
> https://en.wikipedia.org/wiki/Binomial_options_pricing_model
>
> Given its lattice structure, I originally thought of trying a recursive
> implementation, but because it's recombining, the interior nodes would be
> calculated twice.
Looks like a case of Finite Language Syndrome. 'Lattice' has a pretty
specific technical meaning in math, which isn't what's referred to here. If
something on hackage mentions lattice, it's invariably the math meaning.
This 'lattice' of high finance is a tree data structure, in fact, a special
tree you'll probably recognize as Pascal's Triangle.
You might want to look up efficient FP representations of the latter.
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140312/4ff898f3/attachment-0001.html>
------------------------------
Message: 4
Date: Tue, 11 Mar 2014 23:11:31 -0500
From: James Toll <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] library for lattice data structure
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
On Mar 11, 2014, at 8:40 PM, Brent Yorgey wrote:
> I once had a student who implemented exactly this, and did it in a
> clever way---they constructed an actual binary tree data structure,
> but using some "knot-tying" techniques
> (http://www.haskell.org/haskellwiki/Tying_the_Knot) to result in all
> the internal nodes actually being shared in memory. So it really was
> a binary tree data structure but in memory it looked like a lattice.
>
>> I thought this example implementation in Haskell was intriguing but it
>> doesn?t sound as though it?s very quick.
>> http://www.thulasidas.com/2009-03/a-new-kind-of-binomial-tree.htm
>
> You're right; this implementation has the exponential blowup problem.
> However, it's actually possible to take this code and make some simple
> modifications so that it runs quickly, by memoizing the function f.
> One simple way to do that is to replace the function f with lookups
> into an array---the trick is that you can construct the array
> recursively, and thanks to laziness the entries in the array will
> automatically be computed in the right order, so you don't have to
> worry about that like you would in, say, R. For an example, see the
> very last section (titled "Dynamic Programming") on this page:
>
> http://www.cis.upenn.edu/~cis194/lectures/06-laziness.html
>
> -Brent
Brent,
Wow, thank you. I really appreciate your taking the time to provide so much
guidance on the subject. I?m vaguely familiar with memoization, but had not
even heard of ?knot-tying" techniques. So I?ll really have to look into both
topics.
Again, thanks for the guidance. As they say, you don?t know what you don?t
know, so it?s just so helpful to be pointed in the right direction.
Thanks,
James
------------------------------
Message: 5
Date: Tue, 11 Mar 2014 23:35:34 -0500
From: James Toll <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] library for lattice data structure
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
On Mar 11, 2014, at 9:57 PM, Kim-Ee Yeoh wrote:
> Looks like a case of Finite Language Syndrome. 'Lattice' has a pretty
> specific technical meaning in math, which isn't what's referred to here. If
> something on hackage mentions lattice, it's invariably the math meaning.
Yes, I was concerned there might be some conflict between the finance, math
and/or physics terminology. I gave a fair amount of thought to how to refer to
the structure, but in the end just picked lattice because that?s how it?s
referred to in the wikipedia link I included and because I had already read a
lot of quibbling over the use of ?tree?, mostly in the context of binary trees
and binary heaps.
Coming from a finance background, differences in terminology between finance,
physics, math, and statistics is par for the course. I?ll have to be better
about understanding the terminology from a math perspective and will try to
keep that in mind when posting to this list.
Thanks,
James
------------------------------
Message: 6
Date: Wed, 12 Mar 2014 15:19:31 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] library for lattice data structure
Message-ID:
<CAPY+ZdTBv+x3juhyoB1XCLmLBrfR=Y6WRJiY+9Q4USwXCBR=b...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Mar 12, 2014 at 11:35 AM, James Toll <[email protected]> wrote:
> Coming from a finance background, differences in terminology between
> finance, physics, math, and statistics is par for the course. I'll have to
> be better about understanding the terminology from a math perspective and
> will try to keep that in mind when posting to this list.
On deeper reflection, I realize it's more complicated than that. Because
there are
at least two meanings in math.
The lattices on hackage are all about posets and meets and joins, tracing
back to the work of Birkhoff in that subspecialization of algebra known as
order theory.
Then there are the lattices in sphere packings and geometric number theory
and 'lattice'-based cryptography, cf ntru.
One could say that the geometric lattices are closer to binomial lattices,
but not really. I wonder why 'binomial tree' isn't perfectly cromulent.
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140312/49c347bd/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 69, Issue 16
*****************************************
