I am implementing a function that receives a list of list integers and updates the list appending to the ith element a number x, for example:
list = [[1], [], []]
update(list, 0, 3)
> [[1, 3], [], []]
I implemented this in haskell:
updateArray :: Int -> Int -> [[Int]] -> [[Int]]
updateArray idx y [] = []
updateArray idx y arr
| idx < 0 = arr
| idx > (length arr) = arr
| otherwise = updateArray' idx y (length arr) arr
where
updateArray' :: Int -> Int -> Int -> [[Int]] -> [[Int]]
updateArray' idx y n (x:[])
| idx == 0 = (([(x ++ [y])]))
| otherwise = [x]
updateArray' idx y n arr
| n == (idx + 1) = (updateArray' idx y (n - 1) (take (n - 1) arr)) ++ ([((arr !! (n - 1)) ++ [y])])
| otherwise = (updateArray' idx y (n - 1) (take (n - 1) arr)) ++ [arr !! (n - 1)]
Some tests:
ghci> updateArray 2 2 [[], [], [3], [4]]
[[],[],[3,2],[4]]
ghci> updateArray 2 3 [[], [], [3], [4]]
[[],[],[3,3],[4]]
ghci> updateArray 0 7 [[], [], [3], [4]]
[[7],[],[3],[4]]
ghci> updateArray 0 2 [[]]
[[2]]
However I find the code difficult to read. How could I refactor this? And what if the requirement is updated to accept as input list of lists of any type?
1 Answer 1
This started out as a comment, but I figured I'd convert it into an answer. Please pardon the lack of testing: some code I've written may be wrong.
Let's start with your second question,
And what if the requirement is updated to accept as input lists of lists of any type?
I pasted your function into GHCi without type signatures, i.e. omitting the lines
updateArray :: Int -> Int -> [[Int]] -> [[Int]]
updateArray' :: Int -> Int -> Int -> [[Int]] -> [[Int]]
I then asked it for the type
ghci> :t updateArray
updateArray :: Int -> t -> [[t]] -> [[t]]
So your function is already polymorphic. You specialized it more than you needed when you wrote its type signature.
Now to your first question.
How could I refactor this?
My first observation is that your code looks kind of imperative. In particular, it looks like you started with something like
def update_at(idx, y, arr):
if idx < 0 or idx > len(arr):
return arr
else:
return update_at_prime(idx, y, arr)
def update_at_prime(idx, y, arr):
arr_copy = arr[:]
arr_copy[idx] = arr_copy[idx] + [y]
return arr_copy
and then translated it to Haskell. update_at translates almost directly to updateAt, the prime version doesn't quite because Haskell doesn't have as good syntactic sugar for working with lists.
Because Haskell doesn't have this syntactic sugar (or comparable standard library functions -- at least I couldn't find any), you'll need to traverse the list recursively. In a language like Python, you might want to explicitly check the index because you're not explicitly iterating over the list. In Haskell, however, we can move the checks into a base case.
I've refactored your code to do this, plus also to make more use of pattern matching. I also done some small style changes like adding an underscore before variables that aren't going to be used (the compiler should complain about this unless you've disabled that option). One tricky thing here is that that I removed the idx > (length arr) check because if the index is greater than the length of the list, we will end up with the empty list base case. Often (but not always) you won't need to use a function like length in Haskell when you're modifying the elements of a list.
updateArray :: Int -> a -> [[a]] -> [[a]]
updateArray _idx _y [] = []
updateArray idx _y arr
| idx < 0 = arr
updateArray 0 y (x:arr) = (x ++ [y]) : arr
updateArray idx y (x:arr) = x : updateArray (idx - 1) y arr
If I had more time, I would've walked through why the definition of updateArray' was overly complicated. Hopefully the broad strokes are clear.
Now there is a way to do this using a common library called (micro)lens. I'm adding this part for completeness's sake. I expect that if you're asking a question at this level you haven't even heard of lenses. I would focus on understanding my above refactoring instead of this "fancy" way of getting things done.
You can accomplish this by combining ix and over.
import Lens.Micro (ix, over)
updateArray :: Int -> a -> [[a]] -> [[a]]
updateArray idx y arr = over (ix idx) (addElemToEnd y) arr
where
addElemToEnd elem list = list ++ [elem]
Or the shorter way that uses the operator alias for over, which is (%~), and the operator way of writing addElemToEnd.
import Lens.Micro (ix, (%~), (&))
updateArray :: Int -> a -> [[a]] -> [[a]]
updateArray idx y arr = arr & ix idx %~ (++ [y])
Now, lenses are infamously much more difficult to understand than to use. I do not expect you to understand what is going on here, but I would hope that by looking through the documentation and some examples online you could get enough of a gist of them to use them if you desired.