Did I break recursion?

Questions Features & Bugs
,
1

I’m trying to implement a functional zipper:

{-# LANGUAGE UndecidableInstances #-} --needed to derive cofree Show,Eq

module DistrData.Zipper where

import Daml.Control.Recursion
import Daml.Script

data Colist x = Snoc { value : x, prev : Colist x } | Lin deriving (Show, Eq)

type ListZipper x = Cofree (ListF x) (Colist x)

deriving instance (Show x, Show a) => Show (ListF x a)
deriving instance (Show x, Show (f (Cofree f x))) => Show (Cofree f x)

main = script do
  let b = [ "Hello", "world", "!"] 
      zipper : [x] -> ListZipper x = ($ Lin) . cata \case
        Nil -> (`Cofree` Nil)
        Cons x f -> \path -> Snoc x path `Cofree` Cons x (f path)
  debug $ zipper b  --  <-- change `debug` to `pure` fixes this
  assert False
  return ()

And the compiler is complaining on the script:

File:     daml/DistrData/Zipper.daml
Hidden:   no
Range:    15:1-15:5
Source:   Core to DAML-LF
Severity: DsError
Message: 
  Failure to process DAML program, this feature is not currently supported.
  Local variables defined recursively - recursion can only happen at the top level.
  [$dShow1, $dShow2]
damlc: Error when running Shake build system:
BadDependency "GenerateDalf"

It seems to be the debug statement that triggers this, although the error is on line 15 (main). So I suspected that the show instances were somehow to blame. But I’ve managed to separately show both ListF and Cofree, so I’m not certain anymore.

The message however seems to imply local recursion; I can’t see that in the script though. :confused:

2

Should add that cata, Cofree, and ListF are ported form Haskell, here .

3

The issue here is that the instances you defined end up generating mutually recursive definitions between the show instance for ListF and Cofree. The best workaround I could come up with for now is to define more specific instances:

deriving instance Show (Cofree (ListF Text) (Colist Text))
deriving instance Show (ListF Text (Cofree (ListF Text) (Colist Text)))