Псевдонимы полиморфных типов в Haskell

Краткая версия: я хочу псевдоним типа функций type myType = [Int] -> (Tree Int,[Int]), но полиморфно (это означает, что я могу вставить что угодно, а не только Int). Как я мог это сделать?

Длинная версия: у меня сейчас есть:

data Colour = R | B deriving (Show, Read, Eq)
data Tree elt = E | T Colour (Tree elt) elt (Tree elt) deriving (Show, Read, Eq)

type Set a = Tree a

Я хотел бы иметь:

type Funcs = [elt] -> (Tree elt, [elt])

а затем напишите несколько функций, которые будут иметь тип Funcs

treeify_zero :: Treeify_t
treeify_zero lst = (E,lst)

treeify_one :: Treeify_t
treeify_one (h:t) = ((T R E h E), t)

Как это. В настоящее время я не могу заставить type Funcs = forall elt. [elt] -> (Tree elt, [elt]) нормально работать в GHCi. и если я использую type Funcs elt = [elt] -> (Tree elt, [elt]), GHCi жалуется, что мои определения treeify_zero/one "должны иметь 1 аргумент, но не имеют ни одного аргумента. В сигнатуре типа для `to': to::Treeify_t"


types alias haskell
person C.E.Sally    schedule 07.09.2013    source источник
comment
@KarolyHorvath: в моем собственном источнике я назвал его Tre, но подумал, что было бы лучше назвать его Tree, когда задавал вопрос. Я не изменил все экземпляры, приводящие к этим опечаткам. но теперь я их исправил   -  person C.E.Sally    schedule 07.09.2013

Ответы (1)


arrow_upward
2
arrow_downward

Похоже, вы хотите параметризовать синоним типа — elt не может появиться из ниоткуда. Может быть, вы после

type Funcs elt = [elt] -> (Tree elt, [elt])

В качестве альтернативы вам нужен другой связующий, например type Funcs = forall elt. [elt] -> (Tree elt, [elt]). Но вы не сказали, что вы пытаетесь сделать, так что трудно сказать. :-)

person shachaf    schedule 07.09.2013
comment
Ну, я пытаюсь реализовать интересный алгоритм, который преобразует список чего угодно (elt) в набор (с конкретной реализацией упорядоченных красно-черных деревьев) того же чего угодно, и я не уверен, имеет ли это значение, если elt является зависимым типом. В чем разница между вашим первым и последним примерами? в обоих случаях мы получаем полиморфный тип функций, которые переходят от списков к (дереву, списку), верно? - person C.E.Sally; 07.09.2013
comment
Кроме того, я не очень хорошо понимаю type в Haskell. Я бы подумал, что type Funcs elt означает тип функций от elts до пары дерева elt и списка elt. Что именно это означает? - person C.E.Sally; 07.09.2013
comment
@C.E.Sally type Funcs elt = [elt] -> (Tree elt, [elt]) означает, что везде, где вы видите Funcs foo в подписи типа, вы можете заменить его на ([foo] -> (Tree foo, [foo]). - person Daniel Wagner; 07.09.2013
comment
@C.E.Sally Если вы думаете, что Funcs elt заменяет (Tree elt, [elt]), то вы можете увидеть параметр elt в Funcs elt как раскрывающий внутренний тип elt. Это позволяет вам использовать информацию позже, например, такую ​​функцию, как Funcs elt -> Tree elt. Если вы свяжете его с forall, как предлагает @shachaf, тогда elt не сбежит, и если вы попытаетесь написать Funcs -> Tree elt, это будет сложно, поскольку мы не можем быть уверены, что Funcs внутренне использует тот же elt, что и Tree в конечном итоге получает. - person J. Abrahamson; 07.09.2013