News for hackers. Stuff that matters.
Re:Dynamic programming in Haskell: automatic memoization by quchen on Tuesday June 20, 2023 @04:00AM (#36400982)
> If a function has type declaration `f :: A -> B -> C` you would expect that its body only gets evaluated when two arguments are actually supplied.

That’s not correct, regardless of η expansion. The core of the issue is that this function really takes one argument, regardless of how in practice it is used as if it had two.

> the expressions `seq f (putStrLn "hello")` and `seq (f undefined) (putStrLn "hello")` should both not evaluate anything and cause the string hello to be printed rather than raising an exception.

That’s not how `seq` works, as per language report. The definition is very simple, and does not take into account any kinds of types (such as treating functions differently). The report demands that `seq ⊥ x = ⊥` [1], so if the first argument is ⊥, you get a crash. Whether `x` is also evaluated in this context is up to the compiler actually, but what certainly cannot happen is that a "hello" is printed, because that would require a non-⊥ value to be passed to the surrounding IO context, but the whole `seq` is ⊥, so that’s not possible.

In GHC, seq is essentially a tag that helps the strictness analyzer, and hence the optimizer.

There is one subtlety in GHC that makes it not respect η expansion, and that is strictness properties, namely that `seq ⊥ () = ⊥`, but `seq (\x -> ⊥ x) () = ()`, were you referring to that? (In my opinion this is a violation of the Haskell Report.)

> This often occurs in cases where the above hypothetical function `f` requires an intermediate value that's expensive to compute but only relies on the first of its two arguments.

Lookup tables work that way, yes! I’m using this technique for walking a certain distance on a Bezier curve for example (Code at [2], result picture at [3]) Call that academic and I’ll show you the DIN A1 sized CNC machine I control using that logic ;-P

[1]: https://www.haskell.org/onlinereport/haskell2010/haskellch6.... [2]: https://github.com/quchen/generative-art/blob/master/src/Geo... [3]: https://quchen.github.io/generative-art/generative-art-0.1.0...

Re:Dynamic programming in Haskell: automatic memoization by kccqzy on Tuesday June 20, 2023 @12:35PM (#36406630)
Thank you for a long comment. I should've been clearer in my original comment. The crux of the matter is really that the arity of a function should be clear from its type, but those functions violate that assumption. You might think it's not a valid assumption but in practice I think it's a matter of good style to enforce it.

My point about seq is really about arity. If a function has arity 2 then partial application of ⊥ cannot cause any part of the function to be executed and therefore the function cannot inspect its argument and find that it is ⊥.

Re:Dynamic programming in Haskell: automatic memoization by quchen on Tuesday June 20, 2023 @04:20PM (#36409919)
I have to agree that the difference is very subtle, a bit akin to as if "a -> b -> c" is not "a -> (b -> c)". On the other hand, this difference rarely matters, except in memo cases, where it can be used for a pretty cool effect.