Variable re-assignment in an implementation of a list in Haskell-CodePudding

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))

CodePudding user response：

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.

CodePudding user response：

Haskell is pure functional language meaning in short all the values are immutables, they are values. Think of binding names to values, x = 3 means that x is binded to the value 3, and you cannot change that bond. So, what function does in Haskell is transform values. So yes, in this case the tree is entirely "copied" and returned with the modification, example:

data Tree a = EmptyT | Node (Tree a) a (Tree a) deriving Show

replaceFirst x v EmptyT = EmptyT
replaceFirst x v (Node EmptyT tv EmptyT) = if (x == tv) then (Node EmptyT v EmptyT) else (Node EmptyT tv EmptyT)
replaceFirst x v (Node t1 tv EmptyT) = if (x == tv) then (Node t1 v EmptyT) else (replaceFirst x v t1)
replaceFirst x v (Node EmptyT tv t2) = if (x == tv) then (Node EmptyT v t2) else (replaceFirst x v t2)
replaceFirst x v (Node t1 tv t2) = if (x == tv) then (Node (replaceFirst x v t1) v (replaceFirst x v t2)) else (Node (replaceFirst x v t1) tv (replaceFirst x v t2))

Note that you are actually creating a new Tree, and not actually "replacing" the old value with the new one.

try it out:

t1 = Node EmptyT 4 EmptyT
t2 = Node EmptyT 5 EmptyT
t3 = Node t1 7 t2
t4 = Node t3 5 t1


main = putStrLn (show(replaceFirst 4 8 t4))