Haskell problem with potential workaround for empty lists

user_9066972 0
Viewed 84

I defined a function that receives a data type and a list.

getAux :: (Ord a) => SparseArray a -> [Bool] -> (Value a)
getAux (Node x left right) index
 | length(index) == 0 = x
 | head(index) == False = getAux (left) (tail(index))
 | head(index) == True = getAux (right) (tail(index))

I iterate through this function passing the tail of index There are 3 possible returns: If the length of the list is less that or equal to 1 it returns x (the value stored in the node) If not it check the head of index and it calls getAux with the tail of index.

I tried to do a simple workaround to this issue by adding an extra element to the end of index when I call getAux. Instead of comparing if the length of index is equal to 0 I compare it with 1.

When I call the function I have:

getAux (Nodo x iz de) (num2bin(index) ++ [True])

The new getAux is:

getAux :: (Ord a) => SparseArray a -> [Bool] -> (Value a)
getAux (Node x left right) index
 | length(index) == 1 = x
 | head(index) == False = getAux (left) (tail(index))
 | head(index) == True = getAux (right) (tail(index))

In both cases I get an error indicating that I can't do the head of an empty list

list haskell
1 Answers

You call this with tail index, hence eventually you reach the empty list, hence that explains why for the latter, if length index == 1 fails, it will try to access head index and thus error.

But using length is not a good idea since it runs in O(n) with n the length of the list, and usually it is better to perform pattern matching on the list than to use head and tail, since then it is guaranteed that the list has a head and tail.

You can thus implement this as:

getAux :: SparseArray a -> [Bool] -> Value a
getAux (Node x _ _) [] = x
getAux (Node _ left right) (x:xs)
  | x = getAux right xs
  | otherwise = getAux left xs

By turining -Wincomplete-patterns [Haskell-docs] on for the compiler, it will warn you for patterns that the function does not cover. For example if your SparseArray has an extra data constructor, then these cases are not covered (yet).

user_675790
Related