<div dir="ltr"><div><span style="line-height:19.5px">Rein's comment about taking advantage of laziness and sharing over memoization made an impact with me. Seeing it stated like that, it seems obvious. Does anyone know of resources that explain this type of restructuring, preferably with practical examples?</span></div><div><br></div><div>Thanks,</div><div>Jon</div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Apr 11, 2016 at 11:12 PM Rein Henrichs <<a href="mailto:rein.henrichs@gmail.com">rein.henrichs@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I should also mention that many times when you think you want memoization in Haskell, what you actually want is to restructure your computation to take better advantage of laziness (and especially sharing).</div><br><div class="gmail_quote"><div dir="ltr">On Mon, Apr 11, 2016 at 2:10 PM Rein Henrichs <<a href="mailto:rein.henrichs@gmail.com" target="_blank">rein.henrichs@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Compilers generally don't provide memoization optimizations because there isn't a single dominating strategy: it varies on a case-by-case basis. (For example, memoization of some functions can take advantage of structures with sub-linear indexing, but this can't be done generically.)<div><br></div><div>When you can implement your own memoization yourself within the language with exactly the properties you desire (and a number of libraries have already done so for many common strategies ([1], [2], [3], [4])), there has been little motivation to add an implementation to GHC which is either inferior by way of its generality or extremely complex by way of its many special cases.<div><br></div><div>[1]: <a href="https://hackage.haskell.org/package/MemoTrie" target="_blank">https://hackage.haskell.org/package/MemoTrie</a></div><div>[2]: <a href="https://hackage.haskell.org/package/memoize" target="_blank">https://hackage.haskell.org/package/memoize</a></div><div>[3]: <a href="http://hackage.haskell.org/package/data-memocombinators" target="_blank">http://hackage.haskell.org/package/data-memocombinators</a></div><div>[4]: <a href="https://hackage.haskell.org/package/representable-tries" target="_blank">https://hackage.haskell.org/package/representable-tries</a></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Sun, Apr 10, 2016 at 10:06 PM Silent Leaf <<a href="mailto:silent.leaf0@gmail.com" target="_blank">silent.leaf0@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div>I'm sorry to hear, no implicit memoization
(but then is there an explicit approach?). in a pure language, this
seems hardly logical, considering the functional "to one output always
the same result" and the language's propensity to use recursion that uses
then previous values already calculated. Really hope for an explicit
memoization! and i don't mean a manual one ^^ if that is even possible?<br><br>Anyway,
i just don't get your function f. you did get that in mine, xs was the
value of my comprehension list, aka [.s1..n] ++ [0]<br>From there, if
I'm not wrong, your function creates a list of all truncated lists, I
supposed to be used with a call for the nth element? True, it memorizes
all needed things, and in theory only "drops" once per element of the
list.<br><br>As for incorporating it, i'm thinking, local variable? ^^
the function itself could be outside the comprehension list, in a let or
where, or completely out of everything, I don't really see the problem.
then it's just a matter of it being called onto xs inside the
comprehension list, like that:<br>result = [(x,y) | let xs = [1,2,3,0], let yss = f xs, (x,i) <- zip xs [1,2..], y <- yss !! i, x /= y]<br></div>The remaining possible issue is the call to !!... dunno if that's costy or not.<br><br></div>The best way to go through the list I suppose would be by recursion... oh wait, I'm writing as I'm thinking, and I'm thinking:<br>result = [(x,y) | let xs = [1,2,3,0], let yss = f xs, x <- xs, ys <- yss, y <- ys, x /= y]<br></div>after all, why not use the invisible internal recursion? What do you think?<br><br></div>As
for the number-instead-of-number-list, the crucial point i mentioned
was to determine the maximum number of digit (biggest power of ten
reached), and fill up the holes of the smaller numbers with zeroes, so
your examples would be:<br></div>[1,2,3] = 123 --maximum size of a number = 1, no need to fill up<br></div>[12,3]
= 1203 --maximum size of a number = 2 digits, thus the hole beside 3
gets filled with a zero, just like on good old digital watches ^^<br>Do you think extraction of clusters of digits from numbers would be advantageous, efficiently speaking?</div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div></blockquote></div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div>