Haskell считал тип списка
Так, только для забавы, я играл с типом CountedList в Haskell, с помощью чисел Peano и умных конструкторов.
Безопасный с точки зрения типов head и tail просто кажусь действительно спокойным мне.
И я думаю, что достиг предела того, что я знаю, как сделать
{-# LANGUAGE EmptyDataDecls #-}
module CountedList (
Zero, Succ, CountedList,
toList, ofList,
empty, cons, uncons,
head, tail,
fmap, map, foldl, foldr, filter
) where
import qualified List (foldr, foldl, filter)
import Prelude hiding (map, head, foldl, foldr, tail, filter)
data Zero
data Succ n
data CountedList n a = CL [a]
toList :: CountedList n a -> [a]
toList (CL as) = as
ofList :: [a] -> CountedList n a
ofList [] = empty
ofList (a:as) = cons a $ ofList as
empty :: CountedList Zero a
empty = CL []
cons :: a -> CountedList n a -> CountedList (Succ n) a
cons a = CL . (a:) . toList
uncons :: CountedList (Succ n) a -> (a, CountedList n a)
uncons (CL (a:as)) = (a, CL as)
head :: CountedList (Succ n) a -> a
head = fst . uncons
tail :: CountedList (Succ n) a -> CountedList n a
tail = snd . uncons
instance Functor (CountedList n) where
fmap f = CL . fmap f . toList
map :: (a -> b) -> CountedList n a -> CountedList n b
map = fmap
foldl :: (a -> b -> a) -> a -> CountedList n b -> a
foldl f a = List.foldl f a . toList
foldr :: (a -> b -> b) -> b -> CountedList n a -> b
foldr f b = List.foldr f b . toList
filter :: (a -> Bool) -> CountedList n a -> CountedList m a
filter p = ofList . List.filter p . toList
(жаль о любых ошибках записи - машина я первоначально записал это на w/, на который мой компилятор Haskell в настоящее время снижается).
Большая часть того, что я сделал компиляции w/o проблема, но я сталкиваюсь с проблемами с ofList и filter. Я думаю, что понимаю, почему - когда я говорю ofList :: [a] -> CountedList n a, Я говорю ofList :: forall n . [a] -> CountedList n a - то, что созданный список может иметь любой желаемый тип количества. То, что я хочу записать, является эквивалентом псевдо типа ofList :: exists n . [a] -> CountedList n a, но я не знаю как.
Есть ли обходное решение, которое позволило бы мне записать ofList и filter функции как я воображаю, или я достиг предела того, что я могу сделать с этим? У меня есть смысл, что существует некоторый прием с экзистенциальными типами, которые я пропускаю.
2 ответа
Вы не можете написать
ofList :: [a] -> (exists n. CountedList n a) -- wrong
, но вы можете написать
withCountedList :: [a] -> (forall n. CountedList n a -> b) -> b
и передать его функции, которая представляет то, что вы сделали бы с результатом ofList , до тех пор, как его тип не зависит от длина списка.
Кстати, вы можете гарантировать инвариант, что тип из списка соответствует его длине в системе типов, а не полагаться на смарт-конструкторами:
{-# LANGUAGE GADTs #-}
data CountedList n a where
Empty :: CountedList Zero a
Cons :: a -> CountedList n a -> CountedList (Succ n) a
Вы не можете определить ofList или фильтр таким образом, потому что они смущает проверки уровня типа с значениями времени выполнения. В частности, в типе результата CountedList N A , тип n должен быть определен при компиляционном времени. Подразумеваемое желание состоит в том, что n следует соразмерять длительностью списка, который является первым аргументом. Но это явно не может быть известно до времени работы.
Теперь, возможно, можно будет определить типеэкласс, скажем, подсчитанный, а затем (с соответствующим расширением Haskell) определите это как:
ofList :: [a] -> (forall n. (CountedListable CountedList n) => CountedList n a)
, но вам было бы трудно сделать что-либо с таким результатом, поскольку Единственными операциями, которые вызывают . Вы не могли, скажем, получить голову такого значения, потому что голова не может быть определена для всех экземпляров CountedListable