How to define an typeclass instance in Purescript without redundant methods

Question

I'm trying to teach myself Purescript properly. I'm currently working through the Purescript book and am on Chapter 6. Since I'm very familiar with Haskell, the exercises have been pretty easy so far. But I'm currently stuck on one, which I certainly know "how" to do but seem to be defeated by Purescript-specific behaviour regarding defining typeclass instances. And which has made me very curious about how this is done in practice.

The specific thing I'm trying to do is to define a Foldable instance for the NonEmpty type, which is defined like this:

data NonEmpty a = NonEmpty a (Array a)

Coming from a Haskell background, I know foldMap tends to be the simplest way to define Foldable instances, so I took no time to write:

instance foldableNonEmpty :: Foldable NonEmpty where
    foldMap f (NonEmpty a as) = f a <> foldMap f as

which would be sufficient in Haskell, because there are defaults for all the other Foldable methods in terms of foldMap.

I imagined it would be enough in PureScript too, but my code doesn't compile, giving me the error:

  The following type class members have not been implemented:
  foldr :: forall a b. (a -> b -> b) -> b -> ... -> b
  foldl :: forall a b. (b -> a -> b) -> b -> ... -> b

in type class instance

  Data.Foldable.Foldable NonEmpty

This surprised me, seeming inconvenient at best. But I checked the documentation and soon saw that there were indeed predefined ways to get foldl and foldr from foldMap, in the form of foldlDefault and foldrDefault. So my next attempt was:

instance foldableNonEmpty :: Foldable NonEmpty where
    foldMap f (NonEmpty a as) = f a <> foldMap f as
    foldr = foldrDefault
    foldl = foldlDefault

But this, too, fails to compile. The error this time is:

  The value of foldableNonEmpty is undefined here, so this reference is not allowed.

which is a little mysterious to me, but I think it means that I can't yet access foldrDefault and foldlDefault, because (according to the Pursuit documentation) they require the type constructor to already have a Foldable instance, so can't be used as part of defining the instance.

But all this of course begs the question: how can I define a Foldable instance in Purescript without having to manually write out redundant definitions for 2 of the 3 methods? Similarly with other typeclasses that define methods in terms of each other. Or if it is possible (I hope so!), what am I missing?

Actually, after searching Google a bit harder, I did find an example of a Foldable instance, and found that the instance does compile if I do this:

instance foldableNonEmpty :: Foldable NonEmpty where
    foldMap f (NonEmpty a as) = f a <> foldMap f as
    foldr f = foldrDefault f
    foldl f = foldlDefault f

But this begs a new question: since PureScript, as far as I understand it, uses currying in exactly the same way as Haskell, why is this allowed while the "eta-reduced" version above is not? And what does the error message about a value being undefined have to do with anything?

Fyodor Soikin Fyodor Soikin · Accepted Answer · 2020-10-13T20:44:52

Yes, PureScript does use currying in exactly the same way as Haskell, but currying is not the problem here.

The problem is order of evaluation. Haskell uses normal evaluation order, while PureScript uses applicative (in plainer terms - PureScript is not lazy).

This means that Eta-reduction works differently (in edge cases) between PureScript and Haskell. Consider the following example:

f g x = if x > 0 then g x else 0
h x y = f (h x) y

If I call h 5 0, the result is 0, and h is never actually called recursively, because inside f the else branch gets evaluated.

In Haskell this can be safely Eta-reduced:

h x = f (h x)

But if I wrote that in PureScript, it would mean that every call to h x must immediately call h x recursively in order to pass its result to f, thus leading to infinite recursion.

In Haskell this works because h x is not evaluated before being passed into f - aka "normal evaluation order".

It is similar with your class instance, if you remember that instances are just extra parameters that the compiler figures out and passes for you transparently, and that an instance declaration can be seen as a function constructing a dictionary (which is indeed how it's compiled to JavaScript).

In order to call foldrDefault, you must pass it the instance, but this means recursively calling the dictionary-constructing function, which would lead to infinite recursion.

But if you Eta-expand, the instance dictionary is not required during its own construction, but only when foldr is actually called with an argument.

But why in the world would PureScript use applicative evaluation order?! - you might ask indignantly.

Well, I'm not PureScript's designer, so I cannot answer that definitively, but it does make sense to me, considering that it gets compiled to JavaScript, and making the semantics lazy would mean a lot of extra hoops to jump through in the compiled code, which would make it a headache to inspect and debug in the browser.

In response to your comment:

I'm having trouble applying it to the instance definition, in particular why is it that "if you Eta-expand, the instance dictionary is not required during its own construction"? Is that dictionary still not required in order to figure out what foldrDefault actually is?

Perhaps it would be easier to illustrate by looking at compiled JavaScript.

For the Eta-reduced case, the JavaScript would look something like this:

var dictionary = {
    ...
    foldr: foldrDefault(dictionary)
    ...
}

For the Eta-expanded case, the JavaScript would be the following:

var dictionary = {
    ...
    foldr: function(y) { return foldrDefault(dictionary)(y) }
    ...
}

One can see that in the former case the value of dictionary is passed to foldrDefault before the initialization of dictionary is finished. JavaScript actually allows this, and the runtime behavior is that the parameter of foldrDefault would end up being undefined, which of course will lead to a runtime crash.

This was actually a bug in the compiler for a while (I can't find the GitHub issue now, sorry), and the patch was to simply ban this pattern and allow only the Eta-expanded case, in which, as you can see, the value of dictionary gets passed to foldrDefault only then foldr is called, but not during the initialization of dictionary.

How to define an typeclass instance in Purescript without redundant methods

1 Answers