[SOLVED] Variable re-assignment in an implementation of a list in Haskell

Issue

I implemented a binary tree following the instructions of a course I am taking in college (note: it is note the usual binary tree, its a different algorithm but that is not important)
In my set function set :: Eq a => SparseArray a -> Int -> a -> SparseArray a if I use it to update the value of a node what the function will do is make a copy of the tree with the value changed instead of updating the value like it is intended to.

I thought that it would be as easy as using the let ... in notation in the return statement but the program needs to be able to change any variable.

Of course there has to be a solution in the same ways lists are implemented in Haskell.

data Value a = Null | Value a
  deriving (Eq,Read,Show)
data SparseArray a = Vacio | Nodo (Value a) (SparseArray a) (SparseArray a)
  deriving (Eq,Read,Show)

set :: Eq a => SparseArray a -> Int -> a -> SparseArray a 
set Vacio index x = Nodo (Value x) (Vacio) (Vacio)
set (Nodo n iz de) index x
 | index < 0 = Nodo n iz de
 | length(num2bin(index)) == 0 = Nodo (Value x) (iz) (de)
 | head(num2bin(index)) == False && ((Nodo n iz de) == Vacio) = Nodo (Null) (setL (iz) (tail(num2bin(index))) (x)) (de)
 | head(num2bin(index)) == True && ((Nodo n iz de) == Vacio) = Nodo (Null) (iz) (setL (de) (tail(num2bin(index))) (x)) 
 | head(num2bin(index)) == False = Nodo (n) (setL (iz) (tail(num2bin(index))) (x)) (de)
 | head(num2bin(index)) == True = Nodo (n) (iz) (setL (de) (tail(num2bin(index))) (x)) 
 where setL :: Eq a => SparseArray a -> [Bool] -> a -> SparseArray a 
       setL Vacio index x = Nodo (Value x) (Vacio) (Vacio)
       setL (Nodo n iz de) index x
        | length(index) < 0 = Nodo n iz de
        | length(index) == 0 = Nodo (Value x) (iz) (de)
        | head(index) == False && ((Nodo n iz de) == Vacio) = Nodo (Null) (setL (iz) (tail(index)) (x)) (de)
        | head(index) == True && ((Nodo n iz de) == Vacio) = Nodo (Null) (iz) (setL (de) (tail(index)) (x)) 
        | head(index) == False = Nodo (n) (setL (iz) (tail(index)) (x)) (de)
        | head(index) == True = Nodo (n) (iz) (setL (de) (tail(index)) (x)) 

Solution

It is not possible to change a variable in Haskell. That is basically the entire point of Haskell.

Of course there has to be a solution in the same ways lists are implemented in Haskell.

You cannot change a value in a list, either. Try it. There’s no way to do it.

let creates new variables, but it can’t change the values in variables. let ... in ... doesn’t affect anything outside of the ...! Even if you give a new variable the same name as another one – that means code in the ... refers to the new variable, but code outside of the ... refers to the old variable with its old value.

The type signature of your set function shows that it takes a tree as a parameter, and returns a tree. There’s a reason for that: it doesn’t have to return the same tree that is its parameter. You need to return a new tree, but reusing bits of the old tree where possible. Whenever you don’t want to change a branch, you can just use the branch from the old tree in the new tree.

Answered By – user253751

Answer Checked By – Pedro (BugsFixing Volunteer)