Haskell Counted List 유형

Question

그래서 재미를 위해, 나는 Peano 번호를 사용하여 Haskell에서 카운트리스트 유형을 가지고 놀았습니다. 스마트 생성자.

유형-안전 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

(전사 오류에 대해 죄송합니다 - 원래 내가 원래 Haskell 컴파일러에 쓴 기계가 현재 다운되었습니다).

내가 한 일의 대부분은 문제가있는 것과 함께 컴파일하지만 문제가 발생합니다. ofList 그리고 filter. 나는 왜 내가 말할 때 왜 그런지 이해한다고 생각합니다 ofList :: [a] -> CountedList n a, 내가 말하고 있잖아 ofList :: forall n . [a] -> CountedList n a - 생성 된 목록은 원하는 카운트 유형 일 수 있습니다. 내가 쓰고 싶은 것은 의사 유형과 동일합니다. ofList :: exists n . [a] -> CountedList n a, 그러나 나는 방법을 모른다.

내가 쓸 수있는 해결 방법이 있습니까? ofList 그리고 filter 내가 상상하는 것과 같은 기능, 아니면 내가 할 수있는 일의 한계에 도달 했습니까? 나는 약간의 속임수가 있다는 느낌이있다 실존 유형 내가 놓친다.

Answer 1

당신은 쓸 수 없습니다

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

Answer 2

당신은 정의 할 수 없습니다 ofList 또는 filter 이 방법으로 런타임 값으로 유형 수준을 혼동하기 때문입니다. 특히 결과의 유형에서 CountedList n a, 유형 n 컴파일 시간에 결정해야합니다. 암시 적 욕망은 그 것입니다 n 첫 번째 인수 인 목록의 길이에 상응해야합니다. 그러나 런타임까지는 분명히 알 수 없습니다.

이제 타입 클래스를 정의하고 계산 한 다음 (적절한 Haskell 확장자와 함께) 다음과 같은 다음을 정의 할 수 있습니다.

ofList :: [a] -> (forall n. (CountedListable CountedList n) => CountedList n a)

그러나 유일한 작업 이후로 그러한 결과로 무엇이든하는 데 어려움이있을 것입니다 CountedListable 지원은 수를 추출 할 수 있습니다. 당신은 할 수 없었습니다 head 모든 인스턴스에 대해 헤드를 정의 할 수 없기 때문에 그러한 값의 CountedListable