我听过的反对函数式语言的一个论点是,单个赋值编码太难了,或者至少比"普通"编程要难得多.
但是通过我的代码,我意识到如果你用一种合理的现代语言写作,我真的没有很多(任何？)使用模式,使用单一的赋值形式也无法编写.
那么变量的用例有哪些在一个单独的范围调用中变化？请记住,在这种情况下,调用之间不同的循环索引,参数和其他范围限制值不是多个赋值(除非您出于某种原因必须在正文中更改它们),并假设您正在编写某些内容远远高于汇编语言级别,在那里你可以编写类似的东西
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"
当你需要,并有列表推导,地图/收集等等.
您是否发现在这样的环境中仍然需要/需要可变变量,如果是,那么对于什么？
澄清一点,我不是要求对SSA表格的异议进行背诵,而是要求适用这些异议的具体例子.我正在寻找具有可变变量的清晰简洁的代码,如果没有它们就无法编写.
到目前为止我最喜欢的例子(以及我对他们的最佳反对意见):
保罗约翰逊的Fisher-Yates算法答案,当你包含大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的多边形示例区域:
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])]
公主关于用不可变结构实现O(1)队列的难度的观点很有意思(并且很可能提供一个引人注目的例子的基础),但正如所述,它基本上是关于数据结构的可变性,而不是直接关于多重赋值问题.
我对Eratosthenes的回答很感兴趣,但不相信.正如你所引用的论文中给出的那样,正确的大O,拉动尽可能多的素数,无论是否有SSA,都不容易正确实现.
好吧,谢谢大家的尝试.由于大多数答案被证明是1)基于可变数据结构,而不是基于单一指派,2)在某种程度上它们是关于单一指派形式容易被本领域技术人员反击,我将要从我的谈话和/或重组中划线(可能在备份中将其作为讨论主题,在不太可能发生的事情中,在我用完时间之前用完了).
再次感谢.
我遇到的最难的问题是改变列表.所述费-耶茨算法(有时也被称为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
如果你想提出学术论点,那么当然在技术上不必多次分配一个变量.证据是所有代码都可以用SSA(单一静态分配)形式表示.实际上,这是用于多种静态和动态分析的最有用的形式.
同时,有理由我们不能以SSA形式编写代码开头:
以这种方式编写代码通常需要更多语句(或更多行代码).简洁有价值.
它几乎总是效率低下.是的,我知道你在谈论更高级的语言 - 一个公平的范围 - 但即使在Java和C#的世界里,远离集会,速度也很重要.速度无关紧要的应用很少.
这并不容易理解.虽然SSA在数学意义上"更简单",但它从常识中更抽象,这在现实世界的编程中很重要.如果你必须非常聪明地理解它,那么它在编程中没有任何地方.
即使在上面的示例中,也很容易发现漏洞.请你的case发言.如果存在确定是否'*'允许的管理选项,以及是否允许使用单独的管理选项,该'?'怎么办？此外,对于整数情况,不允许为零,除非用户具有允许它的系统权限.
这是一个更加真实的分支和条件示例.你能把它写成一个单独的"声明吗？" 如果是这样,你的"陈述"与许多单独的陈述真的不同吗？如果没有,您需要多少个临时只写变量？那种情况明显好于单一变量吗？
我从来没有发现过这种情况.虽然你总是可以创建新名称,就像转换为SSA形式一样,但我实际上发现每个值都有自己的名称是很容易和自然的.像Haskell这样的语言给了我很多关于命名值的选择,以及两个不同的地方来放置名称绑定(let和where).我发现单一作业形式非常自然而且一点都不困难.
我偶尔会错过能够在堆上指向可变对象的指针.但这些东西没有名字,所以这不是同一个异议.(我还发现,当我在堆上使用可变对象时,我倾向于编写更多错误!)
我认为你会发现最高效的语言可以让你混合功能和命令式的风格,比如OCaml和F#.
在大多数情况下,我可以编写代码,这只是"map x to y,reduce y to z"的长行.在95%的情况下,函数式编程简化了我的代码,但有一个领域不变性显示出来:
实现的容易性和不可变堆栈与不可变队列之间的广泛差异.
堆栈很容易并且与持久性很好地匹配,队列是荒谬的.
不可变队列的最常见实现使用一个或多个内部堆栈和堆栈旋转.好处是这些队列大部分时间都在O(1)中运行,但有些操作将在O(n)中运行.如果您依赖于应用程序中的持久性,那么原则上每个操作都可以在O(n)中运行.当您需要实时(或至少一致)性能时,这些队列并不好.
Chris Okasaki在他的书中提供了不可变队列的实现,他们使用懒惰来实现所有操作的O(1).它是一个非常聪明,相当简洁的实时队列实现 - 但它需要深入了解其底层实现细节,并且它仍然比不可变堆栈更复杂.
相反,我可以使用可变链接列表编写堆栈和队列,这些链接列表在所有操作的恒定时间内运行,并且生成的代码将非常简单.
关于多边形的面积,它易于将其转换为功能形式.我们假设我们有一个这样的Vector模块:
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
我发现这两种功能都不可读.
京公网安备 11010802040832号 | 京ICP备19059560号-6 
