نوع قائمة Haskell المحسوب

Question

لذلك ، فقط للمتعة ، كنت ألعب مع نوع قائمة Counted في 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

(آسف على أي أخطاء في النسخ - الجهاز الذي كتبته في الأصل على W/ My Haskell Lexmented حاليًا).

معظم ما قمت به يجمع مع مشكلة ، لكنني أواجه مشكلات مع 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 يجب أن تكون متنوعة مع طول القائمة التي هي الوسيطة الأولى. ولكن من الواضح أن هذا لا يمكن أن يكون معروفًا حتى وقت التشغيل.

الآن ، قد يكون من الممكن تحديد طبعة طبية ، على سبيل المثال العد ، ثم (مع امتداد هاسكل المناسب) ، حددها مثل:

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

لكن لديك صعوبة في فعل أي شيء مع هذه النتيجة ، لأن العمليات الوحيدة التي CountedListable يمكن أن يكون الدعم هو استخراج العدد. لا يمكنك ، قل احصل على head من هذه القيمة لأنه لا يمكن تعريف الرأس لجميع حالات CountedListable