你是否发现你仍需要可更改的变量?如果是,为什么?

33

我听到过反对函数式语言的一个观点是,单赋值编程太难了,或者至少比“正常”编程要困难得多。

但是看着我的代码,我意识到如果你使用一个相当现代化的语言编写,那么我真的没有许多(或任何?)不能用单赋值形式编写的使用模式。

那么,在作用域的单个调用中变化的变量有哪些用例呢?请记住,循环索引、参数和其他在调用之间变化的作用域绑定值在这种情况下不是多次赋值(除非你必须因为某种原因在主体中改变它们),并且假设你正在使用一个足够高于汇编语言级别的东西,你可以像写html标签一样书写:

values.sum

或者(如果没有提供sum)
function collection.sum --> inject(zero, function (v,t) --> t+v )

并且

x = if a > b then a else b

或者
n = case s 
  /^\d*$/ : s.to_int
  ''      : 0
  '*'     : a.length
  '?'     : a.length.random
  else    fail "I don't know how many you want"

当你需要时,可以使用列表推导式、map/collect等功能。

在这样的环境中,您是否仍然希望/需要可变变量?如果是,是为了什么?

澄清一下,我不是要求重复阐述对SSA形式的反对意见,而是要具体举例说明这些反对意见适用的情况。我正在寻找清晰简洁的代码片段,其中包含可变变量,并且如果没有它们就无法编写。

到目前为止,我最喜欢的例子(也是我期望的最好反驳意见):

  1. Paul Johnson's Fisher-Yates algorithm answer, which is pretty strong when you include the big-O constraints. But then, as catulahoops points out, the big-O issue isn't tied to the SSA question, but rather to having mutable data types, and with that set aside the algorithm can be written rather clearly in SSA:

     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).
    
  2. jpalecek's area of a polygon example:

    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
    }
    

    which might still be written something like:

    def area(figure : List[Point]) : Float = {
        if figure.length < 3
            0
          else
            var a = figure(0)
            var b = figure(1)
            var c = figure(2)
            if figure.length == 3
                magnitude(crossproduct(b-a,c-a))
              else 
                foldLeft((0,a,b))(figure.rest)) { 
                   ((t,a,b),c) => (t+area([a,b,c]),a,c)
                   }
    

    Or, since some people object to the density of this formulation, it could be recast:

    def area([])    = 0.0   # An empty figure has no area
    def area([_])   = 0.0   # ...nor does a point
    def area([_,_]) = 0.0   # ...or a line segment
    def area([a,b,c]) =     # The area of a triangle can be found directly
        magnitude(crossproduct(b-a,c-a))
    def area(figure) =      # For larger figures, reduce to triangles and sum
        as_triangles(figure).collect(area).sum
    
    def as_triangles([])      = []  # No triangles without at least three points
    def as_triangles([_])     = []
    def as_triangles([_,_])   = []
    def as_triangles([a,b,c | rest) = [[a,b,c] | as_triangles([a,c | rest])]
    
  3. Princess's point about the difficulty of implementing O(1) queues with immutable structures is interesting (and may well provide the basis for a compelling example) but as stated it's fundamentally about the mutability of the data structure, and not directly about the multiple assignment issue.

  4. I'm intrigued by the Sieve of Eratosthenes answer, but unconvinced. The proper big-O, pull as many primes as you'd like generator given in the paper he cited does not look easy to implement correctly with or without SSA.


谢谢大家的尝试。由于大部分答案都是基于可变数据结构而非单赋值,且在单赋值形式上容易被熟练掌握技术的从业者反驳,因此我将从我的演讲中删去这一句话,或者重新组织结构(也许可以将其作为备选话题进行讨论,以防在时间用完之前用完所有的词)。

再次感谢。


1
不,它要求提供使用示例模式。 - MarkusQ
我也同意Rich B的观点:这似乎是将“为什么函数式编程如此棒?”转化为网站可接受的形式的尝试。这感觉有些不正当。 - Benjamin Autin
1
@toast 换句话说,你也想不出任何东西。嗯,我想这至少是一个数据点。 - MarkusQ
1
@toast 不,我正在寻找演示材料。我不知道我该如何更清楚地表达这一点。我需要一个难以直接编码为SSA形式的示例。我可以将其放在幻灯片上,而不会有任何Haskell大师立即举手说“你不能只是……” - MarkusQ
1
@MarkusQ:我对你特别强调可变数据结构的好处并不相关感到困惑。可变数据结构及其提供的实际效率显然是任何人想要或需要更改变量的唯一原因。这就像你问电子表格是否比算盘更好,同时又坚持你对计算速度和准确性不感兴趣一样。 - j_random_hacker
显示剩余6条评论
14个回答

18
我遇到的最困难的问题是对列表进行洗牌。Fisher-Yates算法(有时也称为Knuth算法)涉及迭代列表,将每个项目与其他随机项目交换。该算法为O(n),已被广泛知晓并且长期以来已经被证明正确(在某些应用中是一个重要属性)。但它需要可变数组。
这并不意味着您不能在函数式程序中执行洗牌。Oleg Kiselyov 写过此问题。但如果我理解他正确,函数式洗牌是O(n . log n),因为它通过构建二叉树来工作。
当然,如果我需要在Haskell中编写Fisher-Yates算法,我只需将其放入ST monad中,这使您可以将涉及可变数组的算法包装在一个漂亮的纯函数中,例如:
-- | 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

2
+1 是因为你回答了一个比实际问题更有趣的问题(即“在现实生活中,可变数据结构是否会使编程更简单/更快?”),而实际问题由于不透明的原因特别排除了可变数据结构所提供的权衡讨论。 - j_random_hacker

15
如果你想进行学术论证,那么当然不需要给变量分配超过一次的值。证明是所有代码都可以用SSA(单静态赋值)形式表示。事实上,对于许多种静态和动态分析来说,这是最有用的形式。
同时,我们不全都以SSA形式编写代码的原因也很多:
  1. 通常需要更多语句(或更多行代码)来以这种方式编写代码。简洁具有价值。
  2. 它几乎总是效率较低。是的,我知道你在谈论高级语言——公平的范围——但即使在远离汇编语言的Java和C#世界中,速度也很重要。很少有应用程序是速度无关紧要的。
  3. 它不太容易理解。尽管SSA在数学意义上更简单,但它与常识更抽象,而常识才是真实世界编程中最重要的。如果你必须非常聪明才能理解它,那么它在大型编程中就没有位置。
即使在您上面的示例中,也很容易挑出漏洞。以您的case语句为例。如果有一个管理选项决定是否允许'*',另一个管理选项决定是否允许'?'呢?此外,除非用户具有允许它的系统权限,否则不允许整数为零。
这是一个带有分支和条件的更实际的例子。你能将其写成一个单一的"语句"吗?如果可以,你的"语句"是否真的与许多单独的语句不同?如果不行,你需要多少个临时只写变量?而且,这种情况是否比只有一个变量要好得多?

1
我同意你的编号列表是标准答案;我的观点是我发现这在实践中并不成立。这就是为什么我正在寻找适用于这些要点的具体代码示例(特别是要点1和3)。我发现(至少在我的代码中),相反的情况成立。 - MarkusQ
1
至于在case语句示例中“poke holes”的问题,这些规则可以很容易地封装在一个“input_allowed?”函数中,从而产生更清晰的代码,仍然不需要可变变量。 - MarkusQ
好的,请举一个例子,展示你的方法是怎样的,包括我提供的那些具体要求。 - Jason Cohen
请注意:我的观点并不是说使用SSA方式写代码是“不可能的”--当然不是!我的观点是,如果你看一下结果,它并不比通常的方式更好:它不是更简单,也不是更快,也不是更易于维护... - Jason Cohen
假设您同意(尽管我承认这只是一种观点,而且很有争议!),我的问题是:如果它不是这些事情中的任何一件,为什么要这样做?还有什么其他好处使得这是一个良好的权衡? - Jason Cohen

12

我从未遇到过这样的情况。虽然你总是可以像将其转换为SSA形式一样发明新名称,但实际上我发现对于每个值都有自己的名称是很容易和自然的。像Haskell这样的语言让我有很多选择来命名哪些值,并且有两个不同的位置来放置名称绑定(letwhere)。我觉得单赋值形式非常自然,一点也不难。

偶尔我会想念能够在堆上有指向可变对象的指针。但这些东西没有名称,所以这不是同样的反对意见。(而且我也发现当我使用堆上的可变对象时,我倾向于写更多的错误!)


1
因为我没有仔细阅读问题并意识到可变数据结构的权衡讨论已经被排除在外,所以我最初对这个答案感到困惑,因为我知道你意识到即使是O(nlog n)的“随机”访问时间也需要扭曲才能得到真正功能(=持久性)的“可变”数组。你知道有哪些SO问题讨论了这个更有趣的问题(“给出现实生活中可变数据结构更容易/更快的例子”)吗? - j_random_hacker
@j_random 没有头绪。但我怀疑这样的讨论会是无效的,因为它会引出可变数组的支持者。 - Norman Ramsey
不确定您的意思,可变数据结构是一种宗教话题吗? - j_random_hacker
@j_random,是的,在某些人群中,可变与不可变数据结构绝对是一场宗教战争... - Norman Ramsey
1
我明白了,谢谢。这很遗憾,因为它们有一些相当客观的理由(效率)和反对它们的理由(引用透明度)。不同的人有不同的选择! :) - j_random_hacker

6

我认为你会发现,最具生产力的语言允许你混合函数式和命令式风格,例如OCaml和F#。

在大多数情况下,我可以编写代码,它只是一个长长的“将x映射为y,将y归约为z”的行。在95%的情况下,函数式编程简化了我的代码,但有一个领域,不可变性显示出其优势:

实现不可变栈和不可变队列的难度差异很大。

栈很容易且与持久性很好地融合在一起,而队列则非常荒谬。

常见的不可变队列实现使用一个或多个内部栈和栈旋转。好处是这些队列大多数时间以O(1)运行,但某些操作将以O(n)运行。如果您的应用程序依赖于持久性,则原则上每个操作都可能以O(n)运行。当您需要实时(或至少一致)性能时,这些队列就无法胜任了。

Chris Okasaki在他的书《纯函数数据结构》中提供了一个不可变队列的实现,它使用惰性求值来实现所有操作的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

我不觉得这两个函数有任何难以理解的地方。


回复:常数时间队列。2-3指树使用分摊常数时间访问端点和log(min(n1,n2))进行连接。它们也比以前的方法简单得多。可以实现队列。http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html - Chris Smith
@Chris:Okasaki的实时队列是O(1),而指纹树只有平摊O(1)。 - J D

4

使用单一赋值实现那个洗牌算法非常简单,实际上它与命令式解决方案完全相同,只是迭代被重写为尾递归。(使用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).

如果对数组操作的效率有所担忧,那么这是与可变数据结构有关的问题,与单赋值无关。
没有例子可以回答这个问题。这只是熟悉这种风格的问题。

非常好的观点。大O复杂度的考虑与SSA问题并没有直接关联。 - MarkusQ
你怎么能说可变变量是无关紧要的呢?这个问题的标题是“你是否发现仍然需要可以更改的变量,如果是,为什么?”当然,效率考虑也很重要。-1。 - j_random_hacker
非常抱歉,我现在才看到原帖明确排除了可变数据结构的优势作为有效理由。这使得这个问题变得毫无意义,而不是它本来可以成为有趣的权衡讨论。 - j_random_hacker

3
作为对Jason的回应 --
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"

这不是一个讨论论坛。请使用评论或编辑您的问题。 - GEOCHET

3

如果使用非纯函数语言,我会错过一些任务。主要是因为它们会妨碍循环的实用性。例如(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变量。

这些示例可以使用对元组进行折叠来重写,以避免多个赋值,但这实际上并没有提高可读性。


1
你的第一个例子确实可以使用fold重写,虽然不需要元组。你的第二个例子将使用“zipWith foo figure(tail figure)”编写,其中foo使用适当的参数调用crossprod。这比在循环内部放置“last = pt”更清晰。 - Paul Johnson

1

本地(方法)变量确实不必被分配两次。但即使在函数式编程中,重新分配变量也是允许的。不允许的是更改(部分)值。正如dsimcha已经回答的那样,对于非常大的结构(可能在应用程序的根目录),我认为替换整个结构似乎是不可行的。想一想。应用程序的状态最终由应用程序的入口方法包含。如果没有任何状态可以更改而不被替换,您将不得不在每次按键时重新启动应用程序。:(


这个问题并没有回答到点子上:他所说的不是函数式编程,那里重新分配变量可能被允许或不被允许,也不是非函数式(噢...听起来很糟糕)编程,那里重新分配变量可能被允许或不被允许。他所说的是关于重新分配变量是否被允许。如果有帮助的话,可以想象一下 Ruby 或类似的语言,但只能单次赋值。这样行吗?还需要改变什么? - cjs

1
如果您有一个构建惰性列表/树并再次缩减它的函数,那么函数式编译器可能能够使用deforestation进行优化。
如果这很棘手,可能无法优化。那么在性能和内存方面,您就有点倒霉了,除非您可以迭代并使用可变变量。

1
由于图灵完备性定理,我们知道任何可以用图灵完备语言编写的东西都可以用任何图灵完备语言编写。因此,当你深入研究时,你在Lisp中所能做的事情,在C#中也可以做到,只要你足够努力,反之亦然。(更重要的是,在大多数情况下,任何一种语言都将被编译成x86机器语言。)
所以,对于你的问题,答案是:没有这样的情况。所有的情况都更容易让人类理解其中一个范式/语言,而这里的易理解程度与培训和经验有关。

我同意,但正如我在我的答案中所说的那样,这主要是教育和经验的问题。我知道一些只会COBOL的人,他们会更喜欢用COBOL模拟一个HP计算器(尽管有些困难),而不是使用Lisp(他们不熟悉,因此更加困难)。 - Michael Dorfman

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接