1) yes, but that's sumAA's fault, not the data structure; sumAA isn't
tail recursive so it has to build a much bigger stack:
x + (y + (z + (...)))
whereas it could run in constant space if it did this instead:
(...((x + y) + z) + ...)
Usually this transformation is done by passing an
Great thanks, Ryan and Yevgeny!
1. For sumAA 10 $ f 1 2 and for sumAA 1000 $ f 1 2 - does the used
memory amounts differ?
2. Does it create in memory only 2 data objects, or creates 10s and 1000s
and garbage collects unneeded?
--
Also consider
fix (\p - (AA somedata1 $ snd p, BB
Yes.
f somedata1 somedata2 = aa
where aa = AA somedata1 bb
bb = BB somedata2 aa
Spasibo, Yevgeny!
Originally I was thinking theoretically about a single plain
lambda-expression, like
(\ somedata1 somedata2 -
(\ aa bb - aa (bb aa))
(\ b - AA somedata1 b)
(\
Пожалуйста :)
It's difficult to do this in lambda because it isn't expressible in
simply (or even polymorphically) typed lambda calculus, since it
requires the Y (fix) combinator, which introduces non-terminating
computations, whereas simply- and polymorphically-typed lambda
calcules are strongly
On Thu, Jan 29, 2009 at 12:44 AM, Eugene Kirpichov ekirpic...@gmail.com wrote:
With the Y combinator, the code becomes as follows:
f = \somedata1 somedata2 - fst $ fix (\(aa,bb) - (AA somedata1 bb,
BB somedata2 aa))
I tried to prove to myself that the structure really turns out cyclic,
but
Thanks, that clarifies things a lot; I must improve my laziness-fu!
(to Belka: Also, lazy matching may be performed as fix
(\(~(aa,bb)) - ...) - the tilde does the trick)
2009/1/29 Ryan Ingram ryani.s...@gmail.com:
On Thu, Jan 29, 2009 at 12:44 AM, Eugene Kirpichov ekirpic...@gmail.com
Yes.
f somedata1 somedata2 = aa
where aa = AA somedata1 bb
bb = BB somedata2 aa
2009/1/29 Belka lambda-be...@yandex.ru:
Hello!
I'm puzzled, if in Haskell it's possible to create a (pure) data structure,
consisting of 2 substructures referencing each other:
By the way, more advanced stuff of this kind is called Tying the
knot; you can do doubly linked lists with it and much more.
http://www.haskell.org/haskellwiki/Tying_the_Knot
2009/1/29 Belka lambda-be...@yandex.ru:
Hello!
I'm puzzled, if in Haskell it's possible to create a (pure) data
