CODEWITHSUNDEEP
listhaskelltype-inference
Chris Shanks
Chris Shanks

Reputation: 47

Haskell List concatenation Inferred Type

Trying to replace an element within a list at a given point with a new element then return the element.

 setelt :: Int -> [a] -> a -> [a]
 setelt x (yf:(y:yl)) z
   | x == (length yf) = (yf:(z:yl))

Results in this error:

Inferred type is not general enough
Expression    : setelt
Expected type : Int -> [a] -> a -> [a]
Inferred type : Int -> [[a]] -> [a] -> [[a]]

Doesn't seem to have a problem with the concatenation of yf:y:yl so not sure how to solve.

Upvotes: 1

Views: 218

Answers (3)

comingstorm
comingstorm

Reputation: 26117

In addition to problems with pattern matching (for which I also recommend C. A. McCann's answer), your program is probably less efficient than you expect, and certainly less efficient than it could be.

The problem is that Haskell's lists are simple, singly linked lists, which don't carry around their length in a convenient, O(1)-accessible form. Haskell's length must count the number of list nodes, which requires O(N) time. This means that a straightforwardly corrected version of setelt (as provided by Nicolas Dudebout's answer) will scan the remaining list at each step, yielding O(N^2) worst case performance, rather than the O(N) which is possible.

To fix this, scan the list first to get the length. Something like the following implementation, which is O(N) (although using take and drop ends up scanning the list more times than is strictly necessary):

setelt :: Int -> [a] -> a -> [a]
setelt n ys z = front ++ z:back where
  count = length ys - n
  front = take count ys
  (_:back) = drop count ys

Finally, in case it isn't clear: standard Haskell list indexing (as used by take, drop, and!!) starts with 0 at the head of the list, not with 1 at the tail (as appears may be your intent with setelt, and is implemented above). If your intent is to start with 0 at the head, the implementation is easier:

setelt n ys z = front ++ z:back where
    front = take n ys
    (_:back) = drop n ys

or, more efficiently:

setelt 0 (y:ys) z = z:ys
setelt n (y:ys) z = y:setelt (n-1) ys z

Upvotes: 0

Nicolas Dudebout
Nicolas Dudebout

Reputation: 9262

Read C. A. McCann's answer to get some more insight, especially for the problems with lists being too short. Withouth modifying your algorithm, you can fix your code by the simple following change:

 setelt :: Int -> [a] -> a -> [a]
 setelt x (yf:(y:yl)) z
   | x == (length (y:yl)) = (yf:(z:yl))

which can be rewritten succintly:

 setelt :: Int -> [a] -> a -> [a]
 setelt x (yf:ys@(_:yl)) z
   | x == (length ys) = (yf:(z:yl))

Upvotes: 0

C. A. McCann
C. A. McCann

Reputation: 77394

You seem to be misunderstanding what the list constructor (:) does. A Haskell list is a sequence of (:) constructors ending with the empty list [], and pattern matching simply disassembles those constructors in the same order.

So when you pattern match on (yf:(y:yl)) what you're really matching is a list of at least two elements, yf and y, and yl as the rest of the list.

The inferred type is not what you expect because length yf implies that yf--which is the first element of the input list--is itself a list.

What you need to do instead is walk down the list recursively, building a new list using either the current element of the input or the replacement element x when you reach the right location. The general form should look something like the standard library function map, which is implemented as something like this:

map _ [] = []
map f (x:xs) = f x : map f xs

Except that you'll need a way to track what index you're searching for, rather than transforming every element.

Your current function will also fail if applied to a list of 0 or 1 elements, but fixing that should be easy after correcting the algorithm as a whole.

Upvotes: 8

Related Questions