Блог

Я изучаю Хаскелла. У меня есть список, который выглядит так:

 data TwoValueList a = Empty | Node a a (TwoValueList a)  

Я хочу сделать это Foldable так , чтобы я мог выполнять такие вычисления, как:

 sum (Node 0 1 (Node 2 3 Empty)) --should produce 6  

Если бы существовало только одно значение, это было бы легко:

 data OneValueList = Empty | Node a (OneValueList a) instance Foldable OneValueList where  foldr f b Empty = b  foldr f b (Node a rest) = f a (foldr f b rest)  

Однако, если внутри одного узла есть два значения, я не могу точно определить типы , потому f что принимает a и b , но я должен применить f оба a значения внутри TwoValueList и каким-то образом объединить их. Мне не хватает какого-то другого ограничения типа?

Спасибо.

 data TwoValueList a = Empty | Node a a (TwoValueList a)  instance Foldable TwoValueList where  foldr _ ini Empty = ini  foldr f ini (Node x y xs) = f x $ f y $ foldr f ini xs  

Это работает так, что foldr рекурсивно вызывает себя на рекурсивных экземплярах TwoValueList , которые встроены друг в друга до тех пор, пока они не встретятся Empty . В этот момент он возвращает ini начальное значение, и появляется стек вызовов, разрешающий все вызовы функций, описанные выше.

Вместо этого мне проще просто определить foldMap метод:

 data TwoValueList a = Empty | Node a a (TwoValueList a)  instance Foldable TwoValueList where  foldMap _ Empty = mempty  foldMap f (Node x y r) = f x lt;gt; f y lt;gt; foldMap f r  

Просто позвоните f дважды и укажите одно значение для каждого вызова: foldr f b (Node x1 x2 xs) = f x1 (f x2 (foldr f b xs)) .