2

Lets say I have nested lsit: [1, [2, 3, 4], [5, [6]]] and I want to count how many elements it has. In this case it is six elements. I have written such code for doing this:

totalElems :: [a] -> Int
totalElems (x:xs) = case (x, xs) of
                    (_, []) -> 0
                    (y:ys, _) -> 1 + totalElems ys + totalElems xs
                    (_, _) -> 1 + totalElems xs

But I've got an error:

a.hs:4:42:
    Couldn't match expected type ‘a’ with actual type ‘[a0]’
      ‘a’ is a rigid type variable bound by
          the type signature for totalElems :: [a] -> Int at a.hs:1:15
    Relevant bindings include
      xs :: [a] (bound at a.hs:2:15)
      x :: a (bound at a.hs:2:13)
      totalElems :: [a] -> Int (bound at a.hs:2:1)
    In the pattern: y : ys
    In the pattern: (y : ys, _)
    In a case alternative:
        (y : ys, _) -> 1 + totalElems ys + totalElems xs

How I can do this in Haskell?

Improve this question
2
  • 12
    Every element of a list must be the same type. If you want some other structure, you don't want a list.
    – Carl
    Commented Jul 5, 2015 at 21:31
  • 2
    We call those structures trees in haskell.
    – Franky
    Commented Jul 6, 2015 at 5:50

3 Answers 3

Reset to default
7

You can't make freeform lists-within-lists like that in Haskell. Dynamically typed langues will tolerate silliness like that, but strongly-typed Haskell won't.

1 is of type Int, and [2,3,4] is of a different type [Int]. Things in a list have to be of the same type.

However, you could do something like this:

data Nest a = Elem a | List [Nest a]

example ::Nest Int
example = List [Elem 1, List [Elem 2, Elem 3, Elem 4], List [Elem 5, List [Elem 6]]]

countNest :: Nest a -> Int
countNest (Elem x) = 1
countNest (List xs) = sum $ map countNest xs
Improve this answer
8
  • 1
    Your countNest function doesn't count the elements but sums their value.
    – Sven Koschnicke
    Commented Jul 6, 2015 at 9:01
  • Yes, I slightly misread the question. It actually counts now.
    – NovaDenizen
    Commented Jul 6, 2015 at 15:27
  • re "silliness": in a dynamic environment it's just the equivalent of a sum type — why is that silly?
    – Erik Kaplun
    Commented Jul 6, 2015 at 16:11
  • @ErikAllik Sum types are not silly. Keeping your baby food, rat poison, floor wax, and dessert toppings in the same jar is silly.
    – NovaDenizen
    Commented Jul 6, 2015 at 19:19
  • I know what you mean but in a dynamically typed language, the "plain" representation is as good as using "separate jars" — in one way or another you'll end up branching based on the type of the item, regardless of whether it's an actual type check or just a boolean attribute. And it's just as easy to forget the check with or without an additional layer of jars. Or, in other words: [1, [2, 3]] is just as fool proof or error prone as is [Left(1), Right([2, 3])] in a language such as, say, Python. Furthermore, they are semantically isomorphic/equivalent because dynamic languages have RTTI.
    – Erik Kaplun
    Commented Jul 7, 2015 at 10:12
4

Let's say I have nested lsit: [1, [2, 3, 4], [5, [6]]]

You can't have that list. It won't type-check. Try typing it by itself in GHCi; it'll just spit an error message at you. Since this input can't exist in the first place, trying to write a function to process it is a doomed endeavor.

Instead, you need to define a custom data type for this. See the other answers.

Improve this answer
0

As others have said, the simplest way to do this is with a different data structure, like the tree NovaDenizen defined. However, just so you know, Haskell's type system enables various ways of creating "lists" in which the elements have different types : see https://wiki.haskell.org/Heterogenous_collections

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.