CODEWITHSUNDEEP
haskell
Anubhaw Arya
Anubhaw Arya

Reputation: 145

Understanding error in the insertion of an element in a list

So I'm learning haskell right now, and I'm having trouble understanding what I'm doing wrong for the following function that inserts an element x at index k in list l

1.insertElem x k l = take k l ++ (x : drop k l)

2.insertElem x k l = (take k l : x) ++ drop k l

Now, I know that the correct answer is number 1, but I don't understand why number 2 is wrong for the call insertElem 2 5 [0,0,0,0,0,0].

The error is "Cannot construct the infinite type: a ~ [a]. Expected type: [[a]], Actual type: [a]"

Upvotes: 1

Views: 70

Answers (3)

elm
elm

Reputation: 20415

A recursive definition of insertElem that illustrates the use of (:),

insertElem :: a -> Int -> [a] -> [a]
insertElem e 0 xs     = e : xs
insertElem e k []     = [e] -- k > length xs
insertElem e k (x:xs) = x : insertElem e (k-1) xs

Here insertElem delivers a list of a to which we append either the current head of the list of else the actual element to be inserted.

The appending of an element of type a to a list of a uses (:). Note in the second case we append an element e to an empty list, namely [e]; this is equivalent to e : []. In the last case we extract the head of the list also with (:).

Upvotes: 1

Random Dev
Random Dev

Reputation: 52270

Your problem is (as Silvio already told you) the use of : but let's analyse the types to see where the error comes from and how you could see it yourself:

let's check the types

look at

(take k l : x) ++ drop k l

(++) has type [a] -> [a] -> [a] so both parts take k l : x and drop k l need to be lists of the same type.

looking at drop you get Int -> [a] -> [a] so you now know:

  • k has type Int
  • l has type [a]
  • your result is the same type [a]
  • take k l : x too needs to have type [a]

now look at (:) it has type a -> [a] -> [a] so for it to work out you now need x to have type [a] and take k l to have type a.

take has type Int -> [a] -> [a] and we already know that l has type [a] so you get:

  • take k l has type [a]
  • but you also need (see above at (:)) take k l to be of type a

So you need a to be somehow at the same time to be [a] that is what a ~ [a] means and is what the error says.

Upvotes: 7

Silvio Mayolo
Silvio Mayolo

Reputation: 70267

The : operation adds an element (the first argument) to a list (the second argument). Thus, it expects the first argument to be an element and the second to be a list, not the other way around. If you want to do it that way, you would do this:

insertElem x k l = take k l ++ [x] ++ drop k l

Upvotes: 4

Related Questions