5 ms·

Given the laziness, you'd think memoizing an arbitrary pure function would be easy in Haskell - at least as easy as Python, where you can do it with a one line

by klipt 7y ago

Given the laziness, you'd think memoizing an arbitrary pure function would be easy in Haskell - at least as easy as Python, where you can do it with a one line decorator. But no, it's pretty complicated: https://wiki.haskell.org/Memoization https://wiki.haskell.org/Memoization you even have to involve fixed point combinators. Pretty disappointing.

afranchuk 7y ago
Yeah, I think it would need to be a language feature. Otherwise the memoization function itself, with state and conditional execution based on the state, isn't very straightforward.
- rocqua 7y ago
  Best case scenario would be the optimizer does it for you. Less optimal would be compiler hints saying 'please memoize this function'.
- joppy 7y ago
  In simple cases (for example a function UInt8 -> Something) it might be reasonable to expect the optimiser to know how to memoise automatically. But how about functions of the form (Integer -> Something), which have an essentially infinite domain? How much space is the memoization allowed to use? What kind of data structure should be used for the lookup? This could be very hard for the application programmer to communicate to the compiler. Memoising a function f in Haskell can be done like this: create some lazy map where the keys are arguments, and the associated value is f(argument). The function f will only be evaluated once you actually try to use the values of the map.
  - felixschl 7y ago
    I thought the first example in this blog post on TH was an interesting idea: https://www.parsonsmatt.org/2015/11/15/template_haskell.html https://www.parsonsmatt.org/2015/11/15/template_haskell.html
kevmo314 7y ago
Don't you just call a library function? https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-Function-Memoize.html https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-... Just like in Python...?
- owl57 7y ago
  "However, it appears to work." Wow. I don't remember reading such blasphemy in other Haskell docs. And I like it, no joke. Though it's likely about the performance characteristics; memoize probably behaves (and not just appears to behave) like identity modulo performance, that's just not documented clearly enough.
mruts 7y ago
I love FP and have programmed Haskell in professional contexts. But I have to admit, I don’t like it and it’s strong formalisms make so many problems much harder than they have to be. Take lenses for example. All of this unnecessarily complicated shit because Haskell doesn’t have any reasonable record syntax. I appreciate Haskell as a research project and it’s clearly pioneered many important FP concepts: monads, free monads, trampolines, etc. But I would never ever choose it for a new project. OCaml, F#, and Scala would be my go to. Nice FP, but not so opinionated to cripple/slow you down when you want to dip your toes in mutation. And in my experience, almost all non-trivial programs require at least a little bit of mutation. And when it’s required, I really don’t want to waste my time with IORefs or STRefs or whatever.
- antisemiotic 7y ago
  >Take lenses for example. All of this unnecessarily complicated shit because Haskell doesn’t have any reasonable record syntax. Lenses (in the original, pre-Laarhoven form) are literally the same as properties in, say, C#. The extra complexity in their modern form is to pack the setter and getter into a single function, and allow in-place modification (without going throgh getter and then back through setter). The extra-extra complexity in the lens package is the result of Edward Kmett et al generalizing it to support traversals and pattern matching, while also providing support for the entire standard library and the kitchen sink. As for mutation, I agree. I think Rust with hihgher-kinded polymorphism would be my ideal language.
  - foldr 7y ago
    There's always a reason of some kind for the additional complexity. The question is whether it's worth it. > The extra complexity in their modern form is to pack the setter and getter into a single function, and allow in-place modification (without going throgh getter and then back through setter In place updating of nested fields is pretty much the bare minimum that any respectable record system provides.
    - antisemiotic 7y ago
thinkpad20 7y ago
Can you really do it in python with an arbitrary function? What if your function takes a dictionary, set, or some other unhashable type as an argument?
- Veedrac 7y ago
  lru_cache doesn't support unhashable types.
- deleted 7y ago
  [deleted]

by klipt 7y ago

afranchuk 7y ago

Yeah, I think it would need to be a language feature. Otherwise the memoization function itself, with state and conditional execution based on the state, isn't very straightforward.

rocqua 7y ago
Best case scenario would be the optimizer does it for you. Less optimal would be compiler hints saying 'please memoize this function'.
joppy 7y ago
In simple cases (for example a function UInt8 -> Something) it might be reasonable to expect the optimiser to know how to memoise automatically. But how about functions of the form (Integer -> Something), which have an essentially infinite domain? How much space is the memoization allowed to use? What kind of data structure should be used for the lookup? This could be very hard for the application programmer to communicate to the compiler. Memoising a function f in Haskell can be done like this: create some lazy map where the keys are arguments, and the associated value is f(argument). The function f will only be evaluated once you actually try to use the values of the map.
- felixschl 7y ago
  I thought the first example in this blog post on TH was an interesting idea: https://www.parsonsmatt.org/2015/11/15/template_haskell.html https://www.parsonsmatt.org/2015/11/15/template_haskell.html

kevmo314 7y ago

Don't you just call a library function? https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-Function-Memoize.html https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-... Just like in Python...?

owl57 7y ago
"However, it appears to work." Wow. I don't remember reading such blasphemy in other Haskell docs. And I like it, no joke. Though it's likely about the performance characteristics; memoize probably behaves (and not just appears to behave) like identity modulo performance, that's just not documented clearly enough.

mruts 7y ago

I love FP and have programmed Haskell in professional contexts. But I have to admit, I don’t like it and it’s strong formalisms make so many problems much harder than they have to be. Take lenses for example. All of this unnecessarily complicated shit because Haskell doesn’t have any reasonable record syntax. I appreciate Haskell as a research project and it’s clearly pioneered many important FP concepts: monads, free monads, trampolines, etc. But I would never ever choose it for a new project. OCaml, F#, and Scala would be my go to. Nice FP, but not so opinionated to cripple/slow you down when you want to dip your toes in mutation. And in my experience, almost all non-trivial programs require at least a little bit of mutation. And when it’s required, I really don’t want to waste my time with IORefs or STRefs or whatever.

antisemiotic 7y ago
>Take lenses for example. All of this unnecessarily complicated shit because Haskell doesn’t have any reasonable record syntax. Lenses (in the original, pre-Laarhoven form) are literally the same as properties in, say, C#. The extra complexity in their modern form is to pack the setter and getter into a single function, and allow in-place modification (without going throgh getter and then back through setter). The extra-extra complexity in the lens package is the result of Edward Kmett et al generalizing it to support traversals and pattern matching, while also providing support for the entire standard library and the kitchen sink. As for mutation, I agree. I think Rust with hihgher-kinded polymorphism would be my ideal language.
- foldr 7y ago
  There's always a reason of some kind for the additional complexity. The question is whether it's worth it. > The extra complexity in their modern form is to pack the setter and getter into a single function, and allow in-place modification (without going throgh getter and then back through setter In place updating of nested fields is pretty much the bare minimum that any respectable record system provides.
  - antisemiotic 7y ago

thinkpad20 7y ago

Can you really do it in python with an arbitrary function? What if your function takes a dictionary, set, or some other unhashable type as an argument?

Veedrac 7y ago
lru_cache doesn't support unhashable types.
deleted 7y ago
[deleted]