为什么不输入同义词允许在Haskell中递归？ [英] Why don't type synonyms permit recursion in Haskell?

问题描述

  data A ab = A {a :: a，b :: （A a（B a））
 newtype C = C（A Int C）
  

但是我不能通过类型同义词创建类似递归定义的类型？

  type B a = a a（b a）
 type C = A Int C 
  

code> data B a = A {a :: a，b :: B a} 工作得很好。

任何方式来避免在任何地方处理额外的构造函数X我希望类型递归？我主要通过访问函数传递 b ，所以我基本上没问题，但是如果存在一个简单的规避机制，我想知道它。

我应该用什么编译指令来改善专用数据类型C的性能？只是专门化的东西？

在 A ab 和之间进行复制的任何巧妙技巧A cd 只定义 a - > b 和 c - > d 映射而不复制两次记录？我担心 A 的字段将在未来发生变化。模板Haskell也许？ Equi-recursive types 与 iso-recursive types 。 Haskell使用iso-recursive类型实现递归类型，这需要程序员在递归类型发生时告诉类型检查器。你标记它的方式是用一个特定的构造函数，这是一个简单的类型同义词不允许你拥有的。

如果您想要讨论equi和iso递归类型，请查看Benjamin Pierce出色的类型和编程语言

简短回答：因为类型同义词不会引入构造函数， haskell需要构造函数来显式标记类型级别的递归，但不能使用递归类型同义词。

Can anyone explain why these both compile happily :

data A a b = A { a :: a, b :: b }
newtype B a = B (A a (B a))
newtype C = C (A Int C)

But I cannot create a similarly recursively defined types via type synonyms?

type B a = A a (B a)
type C = A Int C

Although obviously data B a = A { a :: a, b :: B a } works just fine.

Is there any way to avoid dealing with that extra constructor X everywhere I want the type recursive? I'm mostly passing in accessor functions that pick out the b anyways, so I'm mostly okay, but if an easy circumvention mechanism exists I'd like to know about it.

Any pragmas I should be using to improve performance with the specialized data type C? Just specialize stuff?

Any clever trick for copying between A a b and A c d defining only the a -> b and c -> d mapping without copying over the record twice? I'm afraid that A's fields will change in future. Template Haskell perhaps?

解决方案

This has to do with Equi-recursive types versus iso-recursive types. Haskell implements recursive types using iso-recursive types, which require the programmer to tell the type-checker when type recursion is happening. The way you mark it is with a specific constructor, which a simple type-synonym doesn't allow you to have.

Equi-recursive types allow the compiler to infer where recursion is happening, but it leads to a much more complicated type-checker and in some seemingly simple cases the problem is undecidable.

If you'd like a good discussion of equi vs. iso recursive types, check out Benjamin Pierce's excellent Types and Programming Languages

Short answer: because type synonyms don't introduce constructors, and haskell needs constructors to explicitly mark recursion at the type-level, you can't use recursive type synonyms.

这篇关于为什么不输入同义词允许在Haskell中递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！