Ch10 Exercise - genericDecode on Tree

Help
#1

I’m attempting this exercise from the PureScript book:

  1. (Medium) The following data type represents a binary tree with values at the leaves:
data Tree a = Leaf a | Branch (Tree a) (Tree a)

Derive Encode and Decode instances for this type using purescript-foreign-generic, and verify that encoded values can correctly be decoded in PSCi.

My solution:

import Data.Generic.Rep (class Generic)
import Data.Generic.Rep.Show (genericShow)
import Foreign.Generic (class Decode, class Encode, F, decodeJSON, defaultOptions, encodeJSON, genericDecode, genericEncode)

data Tree a = Leaf a | Branch (Tree a) (Tree a)

derive instance genericTree :: Generic (Tree a) _

instance decodeTree :: Decode a => Decode (Tree a) where
  decode = genericDecode (defaultOptions { unwrapSingleConstructors = true })

instance encodeTree :: Encode a => Encode (Tree a) where
  encode = genericEncode (defaultOptions { unwrapSingleConstructors = true })

instance showTree :: Show a => Show (Tree a) where
  show = genericShow

But then calling show or encodeJSON triggers what looks like a recursion issue:

> t = Leaf 1                                                                                             
> t                                                                                                      
/home/miles/projects/purescript/psbe/exercises/chapter10/.psci_modules/node_modules/Data.Symbol/index.js:
14                                                                                                       
var IsSymbol = function (reflectSymbol) {
                        ^
RangeError: Maximum call stack size exceeded

Likely related to this issue:

Is there a working solution to this exercise?

#2

Yes, if you include the argument like

decode a = genericDecode (...) a

it should work. This is called eta-expansion. It’s often necessary when writing type class instances for recursive data types.

1 Like
#3

Thanks. Was initially confused in thinking (...) was an operator when trying to get show working.

I couldn’t find any material on eta-expansion in the book. I think one of the following steps needs to be taken to prevent other users from getting stuck:

  • Include an explanation of eta-expansion
  • Remove the exercise
  • Provide some other sort of exercise hint

For reference to others, here’s the modified code:

instance decodeTree :: Decode a => Decode (Tree a) where
  decode a = genericDecode (defaultOptions { unwrapSingleConstructors = true }) a

instance encodeTree :: Encode a => Encode (Tree a) where
  encode a = genericEncode (defaultOptions { unwrapSingleConstructors = true }) a

instance showTree :: Show a => Show (Tree a) where
  show a = genericShow a

Edit: I just realized now that the solution for fixing genericShow was in that github issue, but I didn’t read it closely enough.

#4

Ah sorry about that, I was on my phone and copying all of the actual code was too much of a faff. I agree, this is probably a good opportunity to explain this issue and mention eta-expansion as the fix, because this is something you’re quite likely to run into as a practitioner.

#5

To elaborate a bit on eta-expansion: it’s a term taken from lambda calculus.

Eta-conversion is the general name for the process, and it’s adding or removing an argument to a function in a way that preserves extensional equality (basically: doesn’t change its signature or observed behaviour).

Eta-expansion is adding an argument (f x = g x), eta-reduction would be dropping the argument (f = g).

The reason eta-expansion is a useful/required thing for PS is because the language is not lazy. By introducing the extra argument, it can delay evaluation of the inner function/value, preventing things from being recursive in their definition.

1 Like