您是否发现仍然需要可以更改的变量,如果需要,原因是什么?

我遇到的最困难的问题是把一个列表乱序。这个 Fisher-Yates 算法(有时也称为Knuth算法)涉及到在列表中迭代,将每个项与随机的其他项交换。该算法是O(n),众所周知,并且早就被证明是正确的(在某些应用中这是一个重要的性质)。但它需要可变数组。

这并不是说你不能在一个功能程序中进行洗牌。奥列格·基塞柳夫 written about this . 但如果我理解正确的话,函数式洗牌是O(n.logn),因为它通过构建二叉树来工作。

当然,如果我需要用Haskell编写Fisher-Yates算法,我会把它放在 ST monad mutable arrays 在一个很好的纯函数中,如下所示:

-- | Implementation of the random swap algorithm for shuffling.  Reads a list
-- into a mutable ST array, shuffles it in place, and reads out the result
-- as a list.

module Data.Shuffle (shuffle) where


import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
import System.Random

-- | Shuffle a value based on a random seed.
shuffle :: (RandomGen g) => g -> [a] -> [a]
shuffle _ [] = []
shuffle g xs = 
    runST $ do
      sg <- newSTRef g
      let n = length xs
      v <- newListArray (1, n) xs
      mapM_ (shuffle1 sg v) [1..n]
      getElems v

-- Internal function to swap element i with a random element at or above it.
shuffle1 :: (RandomGen g) => STRef s g -> STArray s Int a -> Int -> ST s ()
shuffle1 sg v i = do
  (_, n) <- getBounds v
  r <- getRnd sg $ randomR (i, n)
  when (r /= i) $ do
    vi <- readArray v i
    vr <- readArray v r
    writeArray v i vr
    writeArray v r vi


-- Internal function for using random numbers
getRnd :: (RandomGen g) => STRef s g -> (g -> (a, g)) -> ST s a
getRnd sg f = do
  g1 <- readSTRef sg
  let (v, g2) = f g1
  writeSTRef sg g2
  return v

如果你想做一个学术性的论证,那么当然,从技术上讲,没有必要多次指定一个变量。证明是所有代码都可以用 SSA (Single Static Assignment) 类型事实上,这是许多静态和动态分析最有用的形式。

同时,有一些原因使我们不能从SSA表单开始编写代码:

1. 以这种方式编写代码通常需要更多的语句(或更多的代码行)。简洁有价值。

即使在上面的例子中,也很容易戳破洞。拿你的 case 陈述如果有一个管理选项决定 '*' 是否允许,以及是否允许 '?' 允许吗?此外,整数情况下不允许为零,除非用户具有允许为零的系统权限。

我从未发现过这样的案例。虽然你总是可以发明新的名称,比如转换成SSA形式,但我发现每个值都有自己的名称是很容易和自然的。像Haskell这样的语言为我提供了很多选择,关于命名哪些值,以及放置名称绑定的两个不同位置( let where ).我觉得单一的作业形式很自然,一点也不难。

我偶尔会错过在堆上拥有指向可变对象的指针。但是这些东西没有名字,所以反对的理由也不一样。(我还发现,当我在堆上使用可变对象时,我倾向于编写更多的bug!)

我认为您会发现,最高效的语言允许您混合使用函数式和命令式风格,例如OCaml和F#。

在大多数情况下,我可以编写简单的代码,即“将x映射到y,将y减少到z”。在95%的情况下,函数式编程简化了我的代码,但有一个领域不变性表现得淋漓尽致:

堆栈很容易,与持久性很好地匹配,队列很可笑。

最 common implementations of immutable queues 大多数时候 ,但某些操作将在O(n)中运行。如果您在应用程序中依赖持久性,那么原则上每个操作都可能在O(n)中运行。当您需要实时(或至少一致)性能时,这些队列是不好的。

his book ,他们使用惰性来实现所有操作的O(1)。这是一个非常聪明、相当简洁的实时队列实现——但它需要对其底层实现细节有深入的理解,而且它仍然比不可变堆栈复杂一个数量级。

module Vector =
    type point =
        { x : float; y : float}
        with
            static member ( + ) ((p1 : point), (p2 : point)) =
                { x = p1.x + p2.x;
                  y = p1.y + p2.y;}

            static member ( * ) ((p : point), (scalar : float)) =
                { x = p.x * scalar;
                  y = p.y * scalar;}

            static member ( - ) ((p1 : point), (p2 : point)) = 
                { x = p1.x - p2.x;
                  y = p1.y - p2.y;}

    let empty = { x = 0.; y = 0.;}
    let to_tuple2 (p : point) = (p.x, p.y)
    let from_tuple2 (x, y) = { x = x; y = y;}
    let crossproduct (p1 : point) (p2 : point) =
        { x = p1.x * p2.y; y = -p1.y * p2.x }

我们可以使用一点元组魔术来定义面积函数:

let area (figure : point list) =
    figure
    |> Seq.map to_tuple2
    |> Seq.fold
        (fun (sum, (a, b)) (c, d) -> (sum + a*d - b*c, (c, d) ) )
        (0., to_tuple2 (List.hd figure))
    |> fun (sum, _) -> abs(sum) / 2.0

或者我们可以用叉积代替

let area2 (figure : point list) =
    figure
    |> Seq.fold
        (fun (acc, prev) cur -> (acc + (crossproduct prev cur), cur))
        (empty, List.hd figure)
    |> fun (acc, _) -> abs(acc.x + acc.y) / 2.0

我不觉得这两个函数都不可读。

这种洗牌算法使用单个赋值实现起来很简单,事实上,它与命令式解决方案完全相同,迭代重写为尾部递归。(Erlang,因为我比Haskell写得更快。)

 shuffle(Lst) ->
     array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).

 shuffle(Array, 0) -> Array;
 shuffle(Array, N) ->
     K = random:uniform(N) - 1,
     Ek = array:get(K, Array),
     En = array:get(N, Array),
     shuffle(array:set(K, En, array:set(N, Ek, Array)), N-1).

如果这些数组操作的效率是一个问题,那么这是一个关于可变数据结构的问题,与单个赋值无关。

你不会得到这个问题的答案,因为没有例子。这只是一个熟悉这种风格的问题。

回应杰森--

function forbidden_input?(s)
    (s = '?' and not administration.qmark_ok) ||
    (s = '*' and not administration.stat_ok)  ||
    (s = '0' and not 'root node visible' in system.permissions_for(current_user))

n = if forbidden_input?(s)
    fail "'" + s + "' is not allowed."
  else
    case s
      /^\d*$/ : s.to_int
      ''      : 0
      '*'     : a.length
      '?'     : a.length.random
      else    fail "I don't know how many you want"

我会错过非纯功能性语言的作业。主要是因为它们阻碍了循环的有效性。示例(Scala):

def quant[A](x : List[A], q : A) = {
  var tmp : A=0
  for (el <- x) { tmp+= el; if(tmp > q) return el; }
  // throw exception here, there is no prefix of the list with sum > q
}

这应该计算列表的分位数,注意累加器 tmp 它被多次分配给。

一个类似的例子是:

def area(figure : List[Point]) : Float = {
  if(figure.empty) return 0
  val last = figure(0)
  var first= figure(0)
  val ret = 0
  for (pt <- figure) {
    ret+=crossprod(last - first, pt - first)
    last = pt
  }
  ret
}

主要注意 last 变量

这些示例可以使用折叠元组来重写,以避免多次赋值,但这实际上无助于可读性。

局部(方法)变量肯定永远不会 有 被分配两次。但即使在函数式编程中,重新分配变量也是允许的。它是 改变 (部分)不允许的值。正如dsimcha已经回答的那样,对于非常大的结构(可能是应用程序的根),替换整个结构对我来说似乎是不可行的。想想看。应用程序的状态最终都包含在应用程序的入口点方法中。如果绝对没有任何状态可以在不被替换的情况下更改,则每次击键都必须重新启动应用程序:(

如果有一个函数构建了一个惰性列表/树,然后又将其缩减,那么函数编译器可以使用 deforestation

如果这很棘手,可能不会。那么你就有点运气不佳,表现不佳;内存方面,除非您可以迭代并使用可变变量。

多亏了Church Turing论文,我们知道任何可以用图灵完整语言编写的东西都可以用 任何

所以,你的问题的答案是:没有这样的情况。所有这些都是人类更容易用一种范式/语言或另一种范式/语言理解的案例——而理解的容易程度与训练和经验有关。

也许这里的主要问题是语言中循环的风格。在使用递归的语言中,当再次调用函数时,在循环过程中更改的任何值都将被重新绑定。在块中使用迭代器的语言(例如Smalltalk和Ruby inject each 和一个可变变量 注射 .

当您使用 while 和 for 另一方面,当您可以将多个参数传递给执行循环一次迭代的代码块时,就不会自动实现变量的轻松重新绑定,因此不可变变量将更加不方便。

在Haskell中工作是研究可变变量必要性的一个非常好的方法,因为默认值是不可变的,但可变变量是可用的(如图所示) IORefs MVars ,等等)。最近我自己就是这样,呃,进行"调查",得出了以下的结论。

1. 在绝大多数情况下,可变变量是不必要的,我很高兴没有它们。

2. 对于线程间通信,可变变量是必不可少的,原因相当明显。(这是Haskell特有的;在最低级别使用消息传递的运行时系统当然不需要它们。)然而,这种使用非常罕见,以至于必须使用函数来读写它们( readIORef fooRef val )不是很大的负担。

所以这些天来,我坚定地站在不可变变量一边。

当您需要对大型数据结构进行小的更改时,该怎么办?您并不希望每次修改几个元素时都复制整个数组或大型类。

我真的没有想过这么多,除非你现在指出了这一点。

实际上,我下意识地试着不使用多个任务。

下面是我所说的python示例

start = self.offset%n
if start:
    start = n-start

我一点也不会错过多项任务。

我知道您要求的代码确实显示了可变变量的好处。我希望我能提供它。但正如前面所指出的,没有什么问题不能用两种时尚来表达。特别是因为你指出,jpalecek的多边形面积示例可以用折叠算法来编写(这是IMHO way messier,它将问题带到了不同的复杂程度)——这让我想知道为什么你对易变性这么难。因此,我将尝试提出一个共同点,以及不可变和可变数据共存的论点。

在我看来,这个问题有点没有抓住要点。我知道,我们的程序员倾向于喜欢干净简单的东西,但有时我们也会忽略混合的可能性。这可能就是为什么在关于不变性的讨论中很少有人持中间立场。我只是想知道为什么,因为让我们面对现实吧- 不变性是一个很好的工具 抽象各种各样的问题。但有时这是一个错误 屁股痛得厉害 . 有时候,这实在太拘束了。仅仅是这一点就让我停下来思考——我们真的想失去可变性吗?真的是非此即彼吗? 难道没有共同点吗 我们能到达吗?什么时候不变性帮助我更快地实现目标,什么时候易变性? (这对我来说是最大的问题)

这些问题中的很多都受到程序员的品味和编程习惯的影响。因此,我将重点关注一个方面,它通常是大多数支持不变性的论点的中心——并行性:

因此,现实世界的并行程序通常有数据图用于确定的单线程操作的区域——因为外部并不知道它们——以及它们可能参与多线程操作的区域(希望只是提供不被操纵的数据)。在这些多线程部件中,我们永远不希望它们发生变化——处理过时的数据比处理不一致的数据要好。这可以通过不变性的概念来保证。

这让我得出了一个简单的结论:对我来说,真正的问题是我所熟悉的编程语言中没有一种允许我说: “在此之后,整个数据结构将是不变的” 和 “在此处为我提供此不可变数据结构的可变副本,请验证只有我才能看到可变副本” . 现在我必须通过翻转一个只读位或类似的东西来保证它。如果我们可以为它提供编译器支持,它不仅可以保证我在翻转所说的位之后没有做任何愚蠢的事情,而且还可以帮助编译器进行以前无法完成的各种优化。另外,对于更熟悉命令式编程模型的程序员来说,该语言仍然具有吸引力。

. 我认为数据应该是 默认情况下是不可变的 编译器应该强制执行这一点,但我们应该有 私有可变表示的概念 ,因为自然存在多线程永远无法达到的领域,而且可读性和可维护性可以从更迫切的结构化中受益。