How do I implement foldr for this particular structure?

user_2026752 0
Viewed 100

I am learning Haskell. I have a list that looks like this:

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

I wish to make this Foldable, such that I might be able to do computations like:

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

If there were only one value, it would be easy:

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)

However, if there are two values inside one node, I can't finegle the types because f takes a and b, but I must apply f to both as inside of the TwoValueList and combine them somehow. Am I missing some other type constraint?

Thank you.

haskell
3 Answers
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

The way this works is that foldr calls itself recursively on recursive instances of TwoValueList that are embeded in each other up until it meets Empty. At that point it returns ini which is the initial value and the call stack comes up resolving all the function calls further above.

user_77556650

I find it easier to just define the foldMap method instead:

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

instance Foldable TwoValueList where
  foldMap _ Empty = mempty
  foldMap f (Node x y r) = f x <> f y <> foldMap f r
user_14776670

Just call f twice and give one value to each call: foldr f b (Node x1 x2 xs) = f x1 (f x2 (foldr f b xs)).

user_75090650
Related