我可以为可以包含自身列表的类型实现 Eq 吗？

Question

此代码无法编译：

data Foo = A String | B (List Foo)

Eq Foo where
  (==) (A x) (A y) = x == y
  (==) (B xs) (B ys) = xs == ys
  (==) _ _ = False

它产生以下错误：

Type checking ./eq.idr eq.idr:11:3-27: | 11 | (==) (A x) (A y) = x == y | ~~~~~~~~~~~~~~~~~~~~~~~~~ Prelude.Interfaces.Main.Foo implementation of Prelude.Interfaces.Eq, method == is possibly not total due to recursive path Prelude.Interfaces.Main.Foo implementation of Prelude.Interfaces.Eq, method == --> Prelude.Interfaces.Main.Foo implementation of Prelude.Interfaces.Eq, method ==

那么这里的问题是我们在其实现中依赖 Eq Foo，因此是递归路径吗？这似乎并没有解释它，因为这个编译：

data Bar = C String | D Bar

Eq Bar where
  (==) (C x) (C y) = x == y
  (==) (D x) (D y) = x == y
  (==) _ _ = False

所以 - 我可以递归调用 == 来定义实现，但我不能列出它？我是否缺少使这项工作成功的技巧，或者我是否正在尝试做一些从根本上被破坏的事情？

Answer 1

判断相等的函数需要用互递归来实现，正如Foo本身就是用互递归来定义的

Eq Foo where
  (==) = eq
    where mutual -- massive indentation necessary
            eq : Foo -> Foo -> Bool
            eq (A l) (A r) = l == r
            eq (B l) (B r) = eq1 l r
            eq _ _ = False 
            eq1 : List Foo -> List Foo -> Bool
            eq1 (l :: ls) (r :: rs) = eq l r && eq1 ls rs
            eq1 [] [] = True
            eq1 _ _ = False

您不能重复使用 List 自己的 (==)，但可以分解出一个模式。

zipWithFoldrElem : (ls : List a) -> (rs : List a) -> ((l : a) -> (r : a) -> Elem (l, r) (zip ls rs) -> b) -> (b -> Lazy b -> b) -> b -> b -> b -> b
zipWithFoldrElem [] [] _ _ e _ _ = e
zipWithFoldrElem [] (_ :: _) _ _ _ el _ = el
zipWithFoldrElem (_ :: _) [] _ _ _ _ er = er
zipWithFoldrElem (l :: ls) (r :: rs) f g e el er = f l r Here `g` zipWithFoldLazyElem ls rs (\l, r, e => f l r (There e)) g e el er

Eq Foo where
  (A l) == (A r) = l == r
  (B l) == (B r) = zipWithFoldrElem l r (f l r) (&&) True False False
   where f : (ls : List Foo) -> (rs : List Foo) -> (l : Foo) -> (r : Foo) -> Elem (l, r) (zip ls rs) -> Bool
         f (l :: _) (r :: _) l r Here = l == r
         f (_ :: ls) (_ :: rs) l r (There e) = f ls rs l r e
         f [] [] _ _ _ impossible
  _ == _ = False

而且，为了展示，这里有一个词典Ord：

Ord Foo where
  compare (A l) (A r) = l `compare` r
  compare (B l) (B r) = zipWithFoldrElem l r (f l r) thenCompare EQ LT GT
    where f : (ls : List Foo) -> (rs : List Foo) -> (l : Foo) -> (r : Foo) -> Elem (l, r) (zip ls rs) -> Ordering
          f (l :: _) (r :: _) l r Here = l `compare` r
          f (_ :: ls) (_ :: rs) l r (There e) = f ls rs l r e
          f [] [] _ _ _ impossible
  compare (A _) (B _) = LT
  compare (B _) (A _) = GT

Answer 2

有一个更好的方法，现在我已经 grokked WellFounded 了一点。

此数据类型之于 Foo 如同 Elem 之于 List。它告诉您在 Foo.

中的何处可以找到子 Foo

-- s is smaller than b if either ...
data Smaller : (s : Foo) -> (b : Foo) -> Type where
  -- it is one of the elements of ss when b = B ss
  Surface : Elem s ss -> Smaller s (B ss)
  -- it is smaller than one of the elements of ms when b = B ms
  -- "m" is for "medium"
  Deeper  : Smaller s m -> Elem m ms -> Smaller s (B ms)

Smaller 是 WellFounded:

WellFounded Smaller where
  wellFounded x = Access (acc x)
    where mutual
            acc : (b : Foo) -> (s : Foo) -> Smaller s b -> Accessible Smaller s
            acc (B ss) s (Surface e) = accSurface ss s e
            acc (B ms) s (Deeper {m} sr e) = accDeeper ms m e s sr
            accSurface : (ss : List Foo) -> (s : Foo) -> Elem s ss -> Accessible Smaller s
            accSurface (s :: _) s Here = Access (acc s)
            accSurface (_ :: ss) s (There e) = accSurface ss s e
            accDeeper : (ms : List Foo) -> (m : Foo) -> Elem m ms -> (s : Foo) -> Smaller s m -> Accessible Smaller s
            accDeeper (m :: _) m Here s sr = acc m s sr
            accDeeper (_ :: ms) m (There e) s sr = accDeeper ms m e s sr

这使用相互递归，就像我以前的回答一样，但它更干净地抽象出来。 WellFounded 实例的一般框架是：

WellFounded (rel : a -> a -> Type) where -- rel s b means s is smaller than b
  wellFounded x = Access (acc x)
    where acc : (b : a) -> (s : a) -> rel s b -> Accessible rel s
    -- Accessible is really cryptic:
    -- Access : (rec : (y : a) -> rel y x -> Accessible rel y) -> Accessible rel x
    -- but the idea of acc is simple:
    -- we convince the totality checker s is really smaller than b
    -- acc needs to be recursive, and when it convinces the totality
    -- checker, it can end with Access (acc s)

WellFounded 买了我们

wfRec : WellFounded rel =>
        (step : (x : a) ->
                (rec : (y : a) -> rel y x -> b) ->
                b
        ) ->
        a -> b

step是开放递归定义的函数。 step 得到一个参数 rec，并且 step 调用 rec 并证明其递归的参数是正确的大小，而不是递归到自身，并且 wfRec 将呼叫路由回 step（本质上是 fix : (step : (rec : (a -> b)) -> (x : a) -> b) -> a -> b; fix f x = f (fix f) x，但总计。）

我们现在可以清楚地分解出列表中 (==) 的逻辑：

eqBy : (ls : List a) -> (rs : List a) -> ((l : a) -> (r : a) -> (el : Elem l ls) -> (er : Elem r rs) -> Bool) -> Bool
eqBy (l :: ls) (r :: rs) eq = eq l r Here Here && eqBy ls rs (\l, r, el, er => eq l r (There el) (There er))
eqBy [] [] _ = True
eqBy _ _ _ = False

而且 Eq 实例并不比天真的实例差多少：

Eq Foo where
  (==) = wfRec step
    where step : (x : Foo) -> ((y : Foo) -> Smaller y x -> Foo -> Bool) -> Foo -> Bool
          step (A l) _ (A r) = l == r
          step (B l) rec (B r) = eqBy l r (\l, r, el, er => rec l (Surface el) r)
          step _ _ _ = False

eqBy 和 WellFounded 实例现在比我之前创建的 zipWithFoldrElem abomination 更加可重用。

我可以为可以包含自身列表的类型实现 Eq 吗？

Can I implement Eq for a type which can contain a list of itself?

idris