[Haskell-beginners] Haskell triangular loop (correct use of (++))

[Rein Henrichs]

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.)

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.

[1]: https://hackage.haskell.org/package/MemoTrie
[2]: https://hackage.haskell.org/package/memoize
[3]: http://hackage.haskell.org/package/data-memocombinators
[4]: https://hackage.haskell.org/package/representable-tries

On Sun, Apr 10, 2016 at 10:06 PM Silent Leaf <silent.leaf0 at gmail.com> wrote:

> 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?
>
> 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]
> 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.
>
> 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:
> result = [(x,y) | let xs = [1,2,3,0], let yss = f xs, (x,i) <- zip xs
> [1,2..], y <- yss !! i, x /= y]
> The remaining possible issue is the call to !!... dunno if that's costy or
> not.
>
> 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:
> result = [(x,y) | let xs = [1,2,3,0], let yss = f xs, x <- xs, ys <- yss,
> y <- ys, x /= y]
> after all, why not use the invisible internal recursion? What do you think?
>
> 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:
> [1,2,3] = 123 --maximum size of a number = 1, no need to fill up
> [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 ^^
> Do you think extraction of clusters of digits from numbers would be
> advantageous, efficiently speaking?
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160411/0d84b4d5/attachment.html>