Как пишут моноид на Scala программисты с разным бэкграундом
isorecursive
Спецификация:
// Хаскелист
trait Monoid[T] {
  val id: T
  def op: T => T => T
}

// Эмельщик
trait Monoid {
  type T
  val id: T
  def op: (T, T) => T
}

// Хардкорный эмельщик
type MONOID = {
  type T
  val id: T
  def op: (T, T) => T
}

// Джавист, прочитавший о self-типах
trait Monoidal[T] { this: T =>
  def op(x: T): T
}

// Джавист, прочитавший о имплицитных вьюхах
abstract class MonoidEnriched[T] {
  def op(y: T): T
}

// Джавист, прочитавший о тайпклассах
trait Monoid[T] {
  val id: T
  def op(x: T, y: T): T
}

// Джавист, прочитавший ещё и о карринге и частичном применении
trait Monoid[T] {
  val id: T
  def op(x: T)(y: T): T
}


Реализация:
// Хаскелист
implicit def list[T] = new Monoid[List[T]] {
  val id = Nil
  def op = xs => xs ++ _
}

// Эмельщик
implicit def list[E] = new Monoid {
  type T = List[E]
  val id = Nil
  def op = _ ++ _
}

// Хардкорный эмельщик
implicit def list[E]: MONOID { type T = List[E] } = new {
  type T = List[E]
  val id = Nil
  def op = _ ++ _
}

// Джавист, прочитавший о self-типах
class MonoidalListAdapter[T](val list: List[T]) extends Monoidal[MonoidalListAdapter[T]] {
  def op(x: MonoidalListAdapter[T]) = new MonoidalListAdapter[T](list ++ x.list)
}

// Джавист, прочитавший о имплицитных вьюхах
abstract class ListMonoidEnriched[T](x: List[T]) extends MonoidEnriched[List[T]] {
  def op(y: List[T]) = x ++ y
}

implicit def list[T](l: List[T]) = new ListMonoidEnriched(l)

// Джавист, прочитавший ещё и о имплицитных классах
implicit class ListMonoidEnriched[T](x: List[T]) extends MonoidEnriched[List[T]] {
  def op(y: List[T]) = x ++ y
}

// Джавист, прочитавший о тайпклассах
implicit def list[T] = new Monoid[List[T]] {
  val id = Nil
  def op(x: List[T], y: List[T]) = x ++ y
}

// Джавист, прочитавший ещё и о карринге и частичном применении
implicit def list[T] = new Monoid[List[T]] {
  val id = Nil
  def op(x: List[T])(y: List[T]) = x ++ y
}


Контекстуализация:
// Ребята с тайпклассами
def f[M](xs: M)(implicit m: Monoid[M]) = m.op(xs, xs) // или m.op(xs)(xs)

// Хардкорный эмельщик
def f[M](xs: M)(implicit m: MONOID { type T = M }) = {
  import m._
  op(xs, xs)
}

// Джавист, прочитавший о self-типах
def f[M <: Monoidal[M]](xs: M) = xs.op(xs)

// Ребята с имплицитными вьюхами и классами
def f[M <% MonoidEnriched[M]](xs: M) = xs.op(xs)

Scala: Call-by-Need
isorecursive
Во время дискуссии пришла идея, как на имплицит-конверсиях реализовать call-by-need:
class ~>[A](delayed: => A) {
  private lazy val value = delayed  
  def force() = value
}

implicit def thunkable[A](computation: => A)  =
  new ~>(computation)

implicit def forceable[A](computation: ~>[A]) =
  computation.force

def lazyInR(x: Int, y: ~>[Int]) = {
  val a = x + 5 * y
  val b = y - 5 * x
  a * b
}

def x: Int = {
  println("I'm printed once!");
  2
}

lazyInR(1, x)

http://www.scalakata.com/509aafece4b093f3524f3a1b

Идея состоит в том, чтобы, подобно встроенному функционалу для by-name, требовать для call-by-need вычислений пометки в сигнатуре типа стрелочкой, только не =>, а ~>, которую мы реализуем классом. Это даёт возможность написать имплицит-конверсии из передаваемого по факту в функцию A в ~>[A] (для задержки), и обратно (для форсирования). В первой конверсии и в конструкторе класса A будет задерживаться by-name благодаря =>. Вторая конверсия - из ~>[A] в A, и она состоит просто в вызове метода force, который содержит логику мемоизированного by-name.

Updated:
Более интересный пример с call-by-need списками: http://www.scalakata.com/509ab47ce4b093f3524f3a24

Совместимость типов ссылок в сабтайпинговых иерархиях узлов деревьёв
isorecursive
Баловался я тут с деревьями, и захотелось мне для узлов АВЛ-дерева реюзнуть структуру и функциональность узлов несбалансированного двоичного дерева поиска. Желание, думаю, очень даже естественное: ведь в узлах АВЛ-дерева всего-то появляется ссылка parent на родительский узел (помимо ссылок left, right на потомков), да height наиболее высокого из двух поддеревьев.
Получилось вот что:
class Node<K> {    
    public K key;
    
    public Node<K> left;
    public Node<K> right;
    
    public Node(K key) {
        this.key = key;
    }            

    public String toString() {
        String leftStr  = left  == null ? "nil" : left.toString(),
               rightStr = right == null ? "nil" : right.toString();            
        return "(" + key.toString() + " " + leftStr + " " + rightStr + ")";
    }
}

class AvlNode<K> extends Node<K> {
    public AvlNode<K> parent;
    public int height = 1;     
    
    public AvlNode(K key) { super(key); }
}

Но вскоре проявляется такая проблема: parent-то у нас нового типа AvlTree, а вот унаследованные left и right - старого Node, и приходится городить даункасты (типа "(AvlNode)left"), а это уже потенциальная дырка в типобезопасности приложения (хотя, конечно, не слишком страшная). Стал я над этой проблемой размышлять и изворачиваться так да сяк, и решил подёргать ассоциированные типы в Scala. Глубокие думы завели меня в дебри грязных фантазий (перегрузка ассоциированного типа в дочернем классе подтипом старого), при исполнении которых, если подумать чуть глубже, система типов была бы явно незвучной. Другая тропинка привела к интересному и простому решению:
abstract class NodeHolder[N] { type Node = Option[N] }

abstract class GBinaryTreeNode[K, N](var key: K) extends NodeHolder[N] {
  var left, right: Node = None  
  
  override def toString() = "(%s %s %s)".format(
    key,
    left  getOrElse "nil",
    right getOrElse "nil"
  )
}

abstract class GAvlNode[K, N](key: K) extends GBinaryTreeNode[K, N](key) {  
  var parent: Node    = None
  var height: Integer = 1
}

class BinaryTreeNode[K](key: K) extends GBinaryTreeNode[K, BinaryTreeNode[K]](key)

class AvlNode[K](key: K) extends GAvlNode[K, AvlNode[K]](key)

Концепция простая: мы до последнего описываем узлы на абстрактном уровне в обобщённых классах (префикс "G" - от слова "Generalized"), параметризованных типом ссылок, и только в конце наследуем от них конкретные, скармливающие при сабтайпинге себя в качестве типа ссылок. А ещё, в корнях наших абстрактных иерархий, мы для красоты и удобства наследуемся от NodeHolder, который вбрасывает в скоуп классов данной иерархии ассоциируемый тип, равный его параметру типа, завёрнутому в Option.

Хоть эта идея пришла в контексте Scala, её можно переписать и на Java, правда не так красиво, и без ассоциируемого типа:
abstract class GBinaryTreeNode<K, N> {
    public K key;
    public N left, right;
    
    public GBinaryTreeNode(K key) { this.key = key; }
    
    public String toString() {
        String leftStr  = left  == null ? "nil" : left.toString(),
               rightStr = right == null ? "nil" : right.toString();            
        return "(" + key.toString() + " " + leftStr + " " + rightStr + ")";
    }
}

abstract class GAvlTreeNode<K, N> extends GBinaryTreeNode<K, N>{        
    public N parent;
    public int height;
    
    public GAvlTreeNode(K key) { super(key); }
}

class BinaryTreeNode<K> extends GBinaryTreeNode<K, BinaryTreeNode<K>> {
    public BinaryTreeNode(K key) { super(key); }
}

class AvlTreeNode<K> extends GAvlTreeNode<K, AvlTreeNode<K>> {
    public AvlTreeNode(K key) { super(key); }
}

Haskell: Generalized Existential Types
isorecursive
С появлением расширения ConstraintKinds появилась возможность написать универсальный экзистеншл под все констрейнты:
data Any c = ∀ a. c a ⇒ Lift a

Здесь 'c' имеет кайнд 'Constraint'. Если сильно хочется, его можно указать явно, импортировав имя 'Constraint' из GHC.Prim и заиспользовав расширение KindSignatures:
data Any (c ∷ * → Constraint) = ∀ a. c a ⇒ Lift a

Погружать внутрь значения можно так же, как в случае обычных экзистеншлов:
a, b, c ∷ Any Show
a = Lift '1'
b = Lift "23"
c = Lift 4

Я несколько раз сталкивался с людьми, которые думают, что каждый раз когда пишешь экзистеншл-обёртку для констрейнта C, нужно писать инстанс C для этой обёртки, который попросту делегирует вызовы завёрнутому значению. Что-то типа такого:
data Showable = ∀ a. Show a ⇒ Showable a

instance Show Showable where
  show (Showable a) = show a

Лучше воздержаться от производства такого бройлерплейта. Ведь с ним даже нельзя будет без распаковывания по-месту-использования вызывать констрейнтанутые функции, не принадлежащие классу. Раньше хорошим решением было под каждый экзистеншл писать, используя Rank2Types, распаковывающий аппликатор, но теперь, когда у нас универсальный экзистеншл, мы можем написать один обобщённый:
(^$) ∷ ∀ c b. (∀ a. c a ⇒ a → b) → Any c → b
f ^$ (Lift x) = f x

Вуаля! Теперь можно писать просто:
d ∷ String
d = show ^$ a ++ concatMap (show ^$) [b, c]

- и так для любых констрейнтов!

Java: Comparable и Comparator
isorecursive
Пока делал дерево поиска, придумал достаточно гибкий компромисс в использовании сабжа. Допустим, есть некий обобщённый класс, на параметре типа которого должно быть определено отношение порядка (в моём случае это параметр К обобщённого класса BinarySearchTree). Можно не заморачиваться и просто писать констрейнт "K extends Comparable<K>", но это не всегда подходит. Дело в том, что если я или пользователь моего дерева захочет использовать в качестве К не принадлежащий ему класс, не реализующий Comparable, он будет вынужден городить адаптер, а это не очень приятно. Даже если бы этой проблемы не было, меня или пользователя моего класса могла бы не устраивать имеющаяся для К реализация Comparable, и хотелось бы иметь также способ использовать альтернативные. Последнюю проблему решает опциональная параметризация дерева Comparator'ами - например, один из конструкторов дерева будет кушать его параметром - но первая проблема останется, ведь даже если инстанцировать дерево этим конструктором, констрейнт на тип К всё-равно останется, и если класс К не мой, а реализации Comparable там нет - я в пролёте. Очевидное решение - удалить констрейнт совсем, а конструктор с компаратором оставить. Но что, если я не хочу каждый раз скармливать компаратор и в случае, если тип реализует Comparable, хочу иметь возможность использовать его функциональность? На помощь приходят джавовские анонимные классы и паттерн "фабричный метод"!
public class BinarySearchTree<K> {
    
    protected final Comparator<K> comparator;
    
    public BinarySearchTree(Comparator<K> comparator) {
        this.comparator = comparator;        
    }
    
    public static <T extends Comparable<T>> BinarySearchTree<T> ofComparable() {
        return new BinarySearchTree<T>(
            new Comparator<T>() {
                public int compare(T a, T b) {
                    return a.compareTo(b);
                };
            }
        );
    }

  ...
}

Вот так-то! Теперь тип К необременён столь строгим констрейнтом, дерево можно параметризовать произвольными кастомными компараторами, но в случае, если тип К всё-таки Comparable (например, Integer), можно, если хочется, инстацировать дерево вот так вот:
BinarySearchTree<Integer> bst = BinarySearchTree.ofComparable();

А нужный компаратор построится исходя из Comparable сам!

You are viewing isorecursive