Ковариантных Дерев в Scala

Question

scalaz.Tree[A] Глядя, она инвариантна в A. Я ищу для многоходового дерева, которое я могу сбросить значение иерархии в

Э.Г. если у меня есть ADT из

trait MyThing 
case object Thing1 extends MyThing 
case object Thing2 extends MyThing 

И я хочу Дерево MyThing с, я не могу использовать это, не делая бросок к MyThing в scalaz;

import scalaz.{Scalaz, Tree} 
import Scalaz._ 
val tree = Thing1.asInstanceOf[MyThing]. 
       node(Thing2.asInstanceOf[MyThing].leaf) 

Это немного боль.

• Есть ли ковариантная [+ A] версия дерева?
• Почему Tree инвариант в первую очередь?

Answer 1

Прежде всего, я хочу, чтобы вторая рекомендация Huw заключалась в том, что вы используете типу, вместо того, чтобы опускаться с asInstanceOf. Как говорит Хув, использование апитера типа не будет выполняться во время компиляции, а не во время выполнения, если что-то изменится в вашей иерархии типов, что делает акты недействительными. Это также хорошая практика, чтобы избежать asInstanceOf для любой upcasts. Вы можете использовать asInstanceOf для повышения или понижения, но только с его использованием для downcasting позволяет легко идентифицировать небезопасное литье в вашем коде.

Чтобы ответить на ваши два вопроса: нет, в Scalaz нет ковариантного типа деревьев по причинам, подробно описанным в pull request, связанным с Huw выше. Поначалу это может показаться огромным неудобством, но решение избежать неинвариантных структур в Scalaz связано с аналогичным дизайнерским решением - избегая использования подтипов в ADT, что делает инвариантные деревья и т. Д. Менее болезненными.

На других языках с хорошей поддержкой ADT (например, Haskell и OCaml, например) листы ADT не являются подтипами типа ADT, а несколько необычная реализация на основе подтипов Scala может привести к ошибочному выводу типа. Ниже является типичным примером этой проблемы:

scala> List(1, 2, 3).foldLeft(None)((_, i) => Some(i)) 
<console>:14: error: type mismatch; 
found : Some[Int] 
required: None.type 
       List(1, 2, 3).foldLeft(None)((_, i) => Some(i)) 
                ^

Поскольку тип аккумулятора выводится из первого аргумента foldLeft, он заканчивается как None.type, который в значительной степени бесполезными. Вы должны указать тип присваивания (или явные параметры типа для foldLeft), что может быть довольно неудобно.

Scalaz пытается решить эту проблему, поощряя использование конструкторов ADT, которые не возвращают наиболее специфичный подтип для листа ADT. Например, он включает в себя none[A] и some[A](a: A) конструкторы для Option, которые возвращают Option[A].

(Для более подробного обсуждения этих вопросов см. Мой ответ here и this related question).

В вашем случае реализации такого подхода может быть столь же просто, как писать следующее:

val thing1: MyThing = Thing1 
val thing2: MyThing = Thing2 

Что позволяет писать thing1.node(thing2.leaf). Если вы хотите пойти дальше по этому пути, я бы настоятельно рекомендовал посмотреть Argonaut's Json ADT как хороший пример дизайна ADT, который уменьшает роль подтипирования.