Haskell 中列表实现中的变量重新分配

Question

我按照大学课程的说明实现了二叉树（注意：请注意通常的二叉树，它是一种不同的算法，但这并不重要）在我的 set 函数 set :: Eq a => SparseArray a -> Int -> a -> SparseArray a 中，如果我使用它来更新节点的值，该函数将做的是复制一个值已更改的树，而不是像预期的那样更新值。

我认为这就像在 return 语句中使用 let ... 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))

Answer 1

无法更改 Haskell 中的变量。这基本上就是 Haskell.

的全部要点

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

您也不能更改列表中的值。尝试一下。没办法。

let 创建新变量，但不能更改变量中的值。 let ... in ... 不会影响 ... 之外的任何内容！即使您为新变量赋予与另一个变量相同的名称 - 这意味着 ... 中的代码引用新变量，但 ... 之外的代码引用具有旧值的旧变量。

您的 set 函数的类型签名表明它以一棵树作为参数，并且 return 是一棵树。这是有原因的：它不必 return 作为其参数的同一棵树。您需要 return 一棵新树，但尽可能重复使用旧树的一些部分。每当你不想改变一个分支时，你可以在新树中使用旧树的分支。

Answer 2

Haskell 是纯函数式语言，简而言之，所有值都是不可变的，它们是值。考虑将名称绑定到值，x = 3 意味着 x 绑定到值 3，并且您无法更改该绑定。因此，Haskell 中的功能是转换值。所以是的，在这种情况下，树被完全“复制”并返回修改，例如：

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

请注意，您实际上是在创建一个新树，而不是用新值“替换”旧值。

试试看：

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

Haskell 中列表实现中的变量重新分配

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

variables

haskell

return

function