CODEWITHSUNDEEP
haskell
Yahatma Amid
Yahatma Amid

Reputation: 39

List Nested Data Type Sum

I have this type

data List a = EmptyL | ConsL a (List (a,a))

and I wrote this function

lenL :: List a -> Int
lenL EmptyL = 0
lenL (ConsL x xs) = 1 + lenL xs

Can I write a function like this?

sumL :: List Int -> Int

How?

Upvotes: 1

Views: 352

Answers (3)

dfeuer
dfeuer

Reputation: 48591

Since sum is a method of Foldable, let's see how we'd implement foldMap:

data List a = EmptyL | ConsL a (List (a,a))

instance Foldable List where
  foldMap _ EmptyL = mempty
  foldMap f (ConsL a as) = f a <> foldMap (\(x,y) -> f x <> f y) as

We can write sumL = getSum . foldMap Sum.

Upvotes: 1

alias
alias

Reputation: 30428

Sure:

data List a = EmptyL | ConsL a (List (a,a))

pair f (x, y) = (f x, f y)

nest :: (a -> b) -> List a -> List b
nest f EmptyL       = EmptyL
nest f (ConsL x xs) = ConsL (f x) (nest (pair f) xs)

sumL :: List Int -> Int
sumL EmptyL       = 0
sumL (ConsL x xs) = x + sumL (nest (uncurry (+)) xs)

We have:

*Main> sumL EmptyL
0
*Main> sumL (ConsL 1 EmptyL)
1
*Main> sumL (ConsL 1 (ConsL (2, 3) EmptyL))
6

The "magic" is explained in: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/efolds.pdf

For completeness, here's a full definition in terms of the generalized fold as described in the paper:

import Prelude hiding (sum, fold)

data List a = EmptyL | ConsL (a, List (a, a))

nest :: (a -> b) -> List a -> List b
nest f EmptyL          = EmptyL
nest f (ConsL (x, xs)) = ConsL (f x, nest (pair f) xs)

pair :: (a -> b) -> (a, a) -> (b, b)
pair f (x, y) = (f x, f y)

fold :: a -> ((b, a) -> a) -> ((b, b) -> b) -> List b -> a
fold e f g EmptyL          = e
fold e f g (ConsL (x, xs)) = f (x, fold e f g (nest g xs))

sum :: List Int -> Int
sum = fold 0 (uncurry (+)) (uncurry (+))

Upvotes: 9

Jonas Dureg&#229;rd
Jonas Dureg&#229;rd

Reputation: 937

The data type you have is not really for lists, more like complete binary trees. You can convert the trees you have to ordinary lists like this:

toList :: List a -> [a]
toList EmptyL = []
toList (ConsL x xs) = x:uncurry (++) (unzip (toList xs))

Not the most efficient code and the ordering is a bit arbitrary, but it should work. If you want the sum or anything else you can just use sum . toList.

Note that your lenL function does not compute the length of the resulting list, but rather the depth of the original tree. If you want the number of elements in the tree you can use length . toList.

Upvotes: 3

Related Questions