ما الخطأ في توقيعات النوع الخاص بي هنا؟

Question

أنا ألعب مع هياكل البيانات corecursive ، وفي وقت مبكر إلى حد ما في الكود الخاص بي ، أحصل على خطأ في النوع:

module Graph where
import Data.Map 

data Node a = Node { getLabel :: a, getInEdges :: [Edge a], getOutEdges :: [Edge a] }
data Edge a = Edge { getStart :: Node a, getEnd :: Node a }
data Graph a = Graph { getNodes :: [Node a], getEdges :: [Edge a] }

mkGraph :: (Ord a) => [(a,a)] -> Graph a
mkGraph pairs = Graph (elems nodes) edges
  where nodes :: Map a (Node a)
        edges :: [Edge a]
        (nodes, edges) = foldr addEdge (empty,[]) pairs
        addEdge :: (a,a) -> (Map a (Node a), [Edge a]) -> (Map a (Node a), [Edge a])
        addEdge (startLabel, endLabel) = undefined

عندما أحاول تحميل هذا في ghci, ، انا حصلت

graph.hs:13:25:
    Couldn't match expected type `forall a. Map a (Node a)'
           against inferred type `Map a (Node a)'
      Expected type: (forall a1. Map a1 (Node a1), forall a1. [Edge a1])
      Inferred type: (Map a (Node a), [Edge a])
    In the expression: foldr addEdge (empty, []) pairs
    In a pattern binding:
        (nodes, edges) = foldr addEdge (empty, []) pairs

إذا قمت بحذف توقيعات النوع nodes :: Map a (Node a) و edges :: [Edge a], ، يختفي الخطأ.

ماذا أفعل خطأ هنا؟ أظن أن نوع المتغير a لا يجري ملزمة mkGraphتوقيع نوع ، ولكن لا ينبغي أن يوضح تعريف mkgraph a في توقيع nodes و edges أن يكون نفسه a?

Answer 1

ماذا أفعل خطأ هنا؟ أظن أن متغير النوع A غير ملزم بتوقيع نوع MkGraph ، لكن ألا ينبغي أن يوضح تعريف mkgraph A في توقيع العقد والحواف ليكون هو نفسه؟

تخمن بشكل صحيح. الأخرى a هو متغير نوع جديد. هذا يعني أنه ليس فقط هو نفسه a كما في mkGraphتوقيع ، إنه جديد تمامًا كمية عالمية اكتب المتغير ، وهو غير صحيح. الأنواع التي تسمى a في توقيعاتك الداخلية ، لا توجد أنواع متعددة الأشكال ولا معروفة واحدة. ولا ، "لا ينبغي" ، وفقًا لمعيار هاسكل. في هاسكل 98 ، من المستحيل في الواقع كتابة توقيع نوع nodes و edges في الكود الخاص بك. نعم ، هذا نوع من السخافة.

ومع ذلك ، توفر GHC أ ScopedTypeVariables امتداد هذا يسمح بذلك ، من بين أشياء أخرى. يناقش القسم ذي الصلة من دليل مستخدم GHC أيضًا مشكلة "توقيع النوع المستحيل" المذكورة أعلاه.

لاحظ أنك ستحتاج أيضًا إلى إضافة صريح forall في نوع التوقيع ل mkGraph, ، بمعنى آخر، forall a. (Ord a) => [(a,a)] -> Graph a لجلب المتغير النوع إلى النطاق. تمكين التمديد وإضافة forall يتيح لك نوع التعليمات البرمجية تحقق لي.