haskell - 您是否发现仍然需要可以更改的变量，如果需要，为什么？

Question

我听到的反对函数式语言的一个论点是，单一赋值编码太难了，或者至少比“普通”编程困难得多。

但是通过我的代码，我意识到我真的没有很多(任何？)使用模式，如果你用一种相当现代的语言编写的话，这些模式不能用单一的赋值形式来编写。

那么在一次调用范围内变化的变量的用例是什么？请记住，在这种情况下，循环索引、参数和其他在调用之间变化的范围绑定(bind)值不是多重赋值(除非您出于某种原因必须在正文中更改它们)，并假设您正在编写一些东西远远高于汇编语言级别，您可以在其中编写诸如

values.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 /收集等。

您是否发现在这样的环境中您仍然想要/需要可变变量，如果是，那是为了什么？

澄清一下，我不是要求背诵对 SSA 表格的反对意见，而是要求这些反对意见适用的具体示例。我正在寻找带有可变变量的清晰简洁的代码，没有它们就无法编写。

到目前为止我最喜欢的例子(以及我期望的最好的反对意见):

保罗·约翰逊的 Fisher-Yates algorithm答案，当您包含大 O 约束时，这非常强大。但是，正如 catulahoops 指出的那样，big-O 问题与 SSA 问题无关，而是与可变数据类型有关，将这些放在一边，算法可以在 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).

jpalecek 的 area of a polygon例子:

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
}

这可能仍然写成:

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

或者，由于有些人反对这个公式的密度，它可以被改写:

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

Princess 关于用不可变结构实现 O(1) 队列的困难的观点很有趣(并且很可能为一个令人信服的例子提供基础)，但正如所述，它基本上是关于数据结构的可变性，而不是直接关于多重分配问题.

我对埃拉托色尼筛法的答案很感兴趣，但不相信。在他引用的论文中给出的合适的 big-O，提取尽可能多的素数生成器在使用或不使用 SSA 的情况下看起来都不容易正确实现。

嗯，谢谢大家的尝试。由于大多数答案被证明是 1)基于可变数据结构，而不是基于单一赋值，以及 2)在某种程度上它们是关于本领域技术人员很容易反驳的单一赋值形式，我将从我的演讲和/或重组中划出界限(也许可以将其作为讨论主题作为备用，以防万一我在时间用完之前用完了单词)。

再次感谢。

Answer 1

我遇到的最困难的问题是洗牌。 Fisher-Yates算法(有时也称为 Knuth 算法)涉及遍历列表，将每个项目与随机的其他项目交换。该算法是 O(n)，众所周知并且长期以来被证明是正确的(在某些应用程序中是一个重要属性)。但它需要可变数组。
这并不是说您不能在函数式程序中进行改组。奥列格·基谢廖夫有 written about this .但如果我正确理解他，功能改组是 O(n . log n) 因为它通过构建二叉树来工作。
当然，如果我需要在 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