Захват правил графика с использованием типов в Scala, OCaml и Haskell

Ответ 1

Я думаю, что самый простой перевод вашей версии Scala использует типы phantom для маркировки node и типа края и привязки их к конкретным конструкторам с помощью GADT.

{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}

data Type = Type1 | Type2

data Edge t where
    EdgeType1 :: Node Type1 -> Node Type2 -> Edge Type1
    EdgeType2 :: Node Type2 -> Node Type1 -> Edge Type2

data Node t where
    NodeType1 :: String -> Node Type1
    NodeType2 :: String -> Node Type2

instance Eq (Node t) where
    NodeType1 a == NodeType1 b = a == b
    NodeType2 a == NodeType2 b = a == b

edgeSource :: Edge t -> Node t
edgeSource (EdgeType1 src _) = src
edgeSource (EdgeType2 src _) = src

main :: IO ()
main = do
    let n1   = NodeType1 "Node1"
        n2   = NodeType2 "Node2"
        edge = EdgeType1 n1 n2
        src  = edgeSource edge

    print $ src == n1

Теперь это более безопасно, чем версия Scala, так как мы знаем точный тип, возвращаемый из edgeSource статически, вместо того, чтобы просто получать абстрактный базовый класс, который нам нужен для ввода типа или шаблона.

Если вы хотите точно воспроизвести версию Scala, вы можете скрыть тип phantom в экзистенциальной оболочке, чтобы вернуть общий "неизвестный" node из edgeSource.

{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE FlexibleInstances #-}

data Some t where
    Some :: t x -> Some t

edgeSource :: Edge t -> Some Node
edgeSource (EdgeType1 src _) = Some src
edgeSource (EdgeType2 src _) = Some src

label :: Node t -> String
label (NodeType1 l) = l
label (NodeType2 l) = l

instance Eq (Some Node) where
    Some n1 == Some n2 = label n1 == label n2

Ответ 2

Изменить: ответ с GADT гораздо более прямым.

Здесь версия Haskell (без unsafeCoerce), которая является одним возможным переводом вашего кода Scala. Однако я не могу помочь с решением OCaml.

Обратите внимание, что в Haskell == не может использоваться для значений другого типа (и способность делать это в Scala часто неодобрительно и источник раздражения и ошибок). Тем не менее, я предложил нижеприведенное решение для сравнения различных типов node, если вам это действительно нужно. Если вам это действительно не нужно, я бы рекомендовал избегать этого, поскольку это зависит от функций/расширений GHC, которые делают ваш код менее переносимым и потенциально могут вызвать проблемы для проверки типов.

БЕЗ полиморфного сравнения node:

{-# LANGUAGE TypeFamilies, FlexibleContexts #-}
-- the FlexibleContexts extension can be eliminated
-- by removing the constraint on edgeSource.

-- let start with just the data types
data NodeType1 = NodeType1 { name1 :: String } deriving Eq
data NodeType2 = NodeType2 { name2 :: String } deriving Eq
data NodeType3 = NodeType3 { name3 :: String } deriving Eq

data EdgeType1 = EdgeType1 { source1 :: NodeType1, target1 :: NodeType2 }
data EdgeType2 = EdgeType2 { source2 :: NodeType2, target2 :: NodeType1 }

-- you tell the compiler that the node types
-- somehow "belong together" by using a type class
class    Node a         where name :: a -> String
instance Node NodeType1 where name = name1
instance Node NodeType2 where name = name2
instance Node NodeType3 where name = name3

-- same about the edges, however in order to
-- map each Edge type to a different Node type,
-- you need to use TypeFamilies; see
-- https://wiki.haskell.org/GHC/Type_families
class Edge a where
  type SourceType a
  -- the constraint here isn't necessary to make
  -- the code compile, but it ensures you can't
  -- map Edge types to non-Node types.
  edgeSource :: Node (SourceType a) => a -> SourceType a

instance Edge EdgeType1 where
  type SourceType EdgeType1 = NodeType1
  edgeSource = source1

instance Edge EdgeType2 where
  type SourceType EdgeType2 = NodeType2
  edgeSource = source2

main = do
  let n1     = NodeType1 "Node1"
      n2     = NodeType2 "Node2"
      edge   = EdgeType1 n1 n2
      source = edgeSource edge
  print (source == n1)  -- True
--  print (source == n2)  -- False  -- DOESN'T COMPILE

С полиморфным node сравнением:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

-- again, constraint not required but makes sure you can't
-- define node equality for non-Node types.
class (Node a, Node b) => NodeEq a b where
  nodeEq :: a -> b -> Bool

-- I wasn't able to avoid OVERLAPPING/OVERLAPS here.
-- Also, if you forget `deriving Eq` for a node type N,
-- `nodeEq` justs yield False for any a, b :: N, without warning.
instance {-# OVERLAPPING #-} (Node a, Eq a)   => NodeEq a a where
  nodeEq = (==)
instance {-# OVERLAPPING #-} (Node a, Node b) => NodeEq a b where
  nodeEq _ _ = False

main = do
  let n1     = NodeType1 "Node1"
      n2     = NodeType2 "Node2"
      edge   = EdgeType1 n1 n2
      source = edgeSource edge
  print (source `nodeEq` n1)  -- True
  print (source `nodeEq` n2)  -- False

Abov - это не единственный способ рассказать системе типа Haskell о ваших ограничениях, например, функциональные зависимости кажутся применимыми, и GADT.

Объяснение:

Стоит понять, почему решение кажется более прямым в Scala.

Scala гибрид между подтипом полиморфизма, основанный на OO, такой как тот, который найден в С++, Java/С#, Python/Ruby и ( часто Haskell - как) функциональное программирование, которое обычно избегает подтипов aka datatype inheritance, и прибегает к другим, возможно лучшим, формам polymorphism.

В Scala способ определения ADT - это кодирование их как sealed trait + ряда (потенциально запечатанных) классов case и/или объектов case. Однако это только чистый ADT, только если вы никогда не ссылаетесь на типы объектов case и классов case, чтобы притворяться, что они похожи на Haskell или ML ADT. Однако ваше решение Scala действительно использует эти типы, то есть указывает на "ADT".

В Haskell нет никакого способа сделать это, поскольку отдельные конструкторы ADT не имеют определенного типа. Вместо этого, если вам нужно ввести различение между отдельными конструкторами ADT, вам необходимо разбить исходный ADT на отдельные ADT, по одному на каждый конструктор исходного ADT. Затем вы группируете эти ADT вместе, чтобы иметь возможность ссылаться на все их в ваших подписях типа, помещая их в класс type, который является формой ad-hoc-полиморфизма.

Ответ 3

Вы спрашивали слишком много о системе типа Ocaml. На этом этапе вашей второй попытки:

let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) -> 

вы говорите: должно быть ясно, что src имеет node_type_1, и я дал тип возврата node, поэтому компилятор должен иметь возможность отсортировать правильный конструктор для использования с типом src. Однако это вообще невозможно: в данном варианте нет уникального отображения от "типов членов" к конструкторам; например: type a = A of int | B of int. Поэтому вам нужно указать конструктор (вы могли бы назвать его короче).

Если вы не хотите, чтобы вы использовали полиморфизм. Один из вариантов делает функцию src_link полиморфной. Одна попытка -

type e12 = node_type_1 * node_type_2
type e21 = node_type_2 * node_type_1

let link_source = fst

но тогда вы должны разоблачить типы ссылок в виде кортежей отдельно. Другой вариант - использовать полиморфные варианты.

type node1 = [`N1 of string]
type node2 = [`N2 of string]
type node3 = [`N3 of string]
type node = [node1 | node2 | node3]
type edge = E12 of node1 * node2 | E21 of node2 * node1

то можно было бы написать

let link_source (e:edge) : [<node] = match e with
  | E12 (`N1 s, _) -> `N1 s 
  | E21 (`N2 s, _) -> `N2 s

это автоматически объединяет тип возврата и проверяет, существует ли он node. Последнее совпадение с шаблоном также можно обрабатывать с помощью принуждения типа:

let link_source (e:edge) : node = match e with
  | E12 (n1, _) -> (n1:>node)
  | E21 (n2, _) -> (n2:>node)

GADT также могут помочь. С теми же определениями для node{,1,2,3} выше можно определить

type ('a, 'b) edge =
  | E12 : node1 * node2 -> (node1, node2) edge
  | E21 : node2 * node1 -> (node2, node1) edge

а затем полиморфный

let link_source : type a b . (a, b) edge -> a = function
  | E12 (n1, _) -> n1
  | E21 (n2, _) -> n2

: при использовании GADT нет необходимости использовать полиморфные варианты. Таким образом, можно просто

type node1 = N1 of string
type node2 = N2 of string
type node3 = N3 of string

и те же определения edge и link_source будут работать.