هاسكل: خلق نوع فئات للسحابات

Question

وهكذا لقد كنت أقرأ قليلا عن نمط زيبر في هاسكل (واللغات وظيفية أخرى، وأفترض) لاجتياز وتعديل هيكل البيانات، واعتقدت أن هذا سيكون فرصة جيدة بالنسبة لي لصقل مهاراتي في إنشاء فئات نوع في هاسكل، منذ الطبقة يمكن أن يقدم واجهة اجتياز المشتركة بالنسبة لي لكتابة التعليمات البرمجية ل، بغض النظر عن بنية بيانات اجتاز.

وظننت أنني كنت على الأرجح بحاجة إلى فئتين - واحدة للبنية البيانات الجذر، واحد لبنية البيانات الخاصة التي تم إنشاؤها لاجتياز أول:

module Zipper where

class Zipper z where
  go'up :: z -> Maybe z
  go'down :: z -> Maybe z
  go'left :: z -> Maybe z
  go'right :: z -> Maybe z

class Zippable t where
  zipper :: (Zipper z) => t -> z
  get :: (Zipper z) => z -> t
  put :: (Zipper z) => z -> t -> z

ولكن عندما حاولت هذه مع بعض datastructures بسيطة مثل القائمة:

-- store a path through a list, with preceding elements stored in reverse
data ListZipper a = ListZipper { preceding :: [a], following :: [a] }

instance Zipper (ListZipper a) where
  go'up ListZipper { preceding = [] } = Nothing
  go'up ListZipper { preceding = a:ps, following = fs } = 
      Just $ ListZipper { preceding = ps, following = a:fs }
  go'down ListZipper { following = [] } = Nothing
  go'down ListZipper { preceding = ps, following = a:fs } = 
      Just $ ListZipper { preceding = a:ps, following = fs }
  go'left _ = Nothing
  go'right _ = Nothing

instance Zippable ([a]) where
  zipper as = ListZipper { preceding = [], following = as }
  get = following
  put z as = z { following = as }

وأو شجرة ثنائية:

-- binary tree that only stores values at the leaves
data Tree a = Node { left'child :: Tree a, right'child :: Tree a } | Leaf a
-- store a path down a Tree, with branches not taken stored in reverse
data TreeZipper a = TreeZipper { branches :: [Either (Tree a) (Tree a)], subtree :: Tree a }

instance Zipper (TreeZipper a) where
  go'up TreeZipper { branches = [] } = Nothing
  go'up TreeZipper { branches = (Left l):bs, subtree = r } =  
      Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } }
  go'up TreeZipper { branches = (Right r):bs, subtree = l } =  
      Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } }
  go'down TreeZipper { subtree = Leaf a } = Nothing
  go'down TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } =
      Just $ TreeZipper { branches = (Right r):bs, subtree = l }
  go'left TreeZipper { branches = [] } = Nothing
  go'left TreeZipper { branches = (Right r):bs } = Nothing
  go'left TreeZipper { branches = (Left l):bs, subtree = r } =
      Just $ TreeZipper { branches = (Right r):bs, subtree = l }
  go'right TreeZipper { branches = [] } = Nothing
  go'right TreeZipper { branches = (Left l):bs } = Nothing
  go'right TreeZipper { branches = (Right r):bs, subtree = l } =
      Just $ TreeZipper { branches = (Left l):bs, subtree = r }

instance Zippable (Tree a) where
  zipper t = TreeZipper { branches = [], subtree = t }
  get TreeZipper { subtree = s } = s
  put z s = z { subtree = s }

وأنا لم أستطع الحصول عليه لتجميع، كنت مجرد الحصول على الكثير من الأخطاء مثل هذا لكل من بلدي Zippable تعريفات سبيل المثال:

Zipper.hs:28:14:
    Couldn't match expected type `z'
           against inferred type `ListZipper a'
      `z' is a rigid type variable bound by
          the type signature for `zipper' at Zipper.hs:10:20
    In the expression: ListZipper {preceding = [], following = as}
    In the definition of `zipper':
        zipper as = ListZipper {preceding = [], following = as}
    In the definition for method `zipper'

لذلك أنا لست متأكدا من أين نذهب من هنا. وأظن أن قضيتي هي أن أحاول ربط هاتين الحالتين معا، عندما إعلان (Zipper z) => فقط يريد z أن يكون أي Zipper.

Answer 1

(وبصرف النظر:. مخطط go'up تسمية الخاص بك هو ... ابتكارا أسلوب هاسكل عادة camelCase)

وأنت على الطريق الصحيح. ما كنت قد كتبت ما يعادل أدناه.

{-# LANGUAGE RankNTypes #-}
instance Zippable [a] where
    zipper = ... :: forall z. (Zipper z) => [a] -> z
    get = ... :: forall z. (Zipper z) => z -> [a]
    set = ... :: forall z. (Zipper z) => z -> [a] -> z

و(لجميع أنواع z، Zipper z معين، ويوجد zipper :: [a] -> z).

أنت ترينغ لتحديد zipper = ... :: [a] -> ListZipper a، التي من الواضح أنها ضيقة للغاية.

وسوف التعليمات البرمجية typecheck مع تغيرات طفيفة التالية:

{-# LANGUAGE MultiParamTypeClasses #-}
class (Zipper z) => Zippable z t where
    zipper :: t -> z
    get :: z -> t
    set :: z -> t -> z
instance Zippable (ListZipper a) [a] where
    ...
instance Zippable (TreeZipper a) (Tree a) where
    ...

الطبقات نوع متعددة المعلمة . انها امتداد ما بعد Haskell'98، ولكن تطبيقات هاسكل دعم على نطاق واسع.

Answer 2

ويمكنك أيضا استخدام نوع العائلات مرادف بدلا من نوع فصول متعددة المعلمة والاعتماد الوظيفي. في مثل هذه الحالات أنها توفر حلا أنظف وأسهل في الفهم. في هذه الحالة الطبقة والمثال ستصبح:

class Zippable t where
  type ZipperType t :: *
  enter :: t -> ZipperType t
  focus :: ZipperType t -> t

instance Zippable [a] where
  type ZipperType [a] = ListZipper a
  enter = ...
  focus = ...

المرح مع وظائف نوع هو مقدمة ممتازة لكتابة العائلات مرادف للناس بالفعل على دراية هاسكل. كتبت أيضا مقال حول كيفية نوع وغالبا ما أسر مرادف أن تستخدم بدلا من الاعتماد الوظيفي منذ فترة.

وآمل أن يساعد هذا!