我最近一直在阅读很多关于函数式编程的东西,我可以理解它的大部分内容,但是我无法解决的一件事就是无状态编码.在我看来,通过删除可变状态简化编程就像通过删除仪表板来"简化"汽车:成品可能更简单,但运气好,使其与最终用户交互.
几乎我能想到的每个用户应用程序都将状态作为核心概念.如果您编写文档(或SO帖子),状态将随每个新输入而变化.或者,如果你玩视频游戏,有很多状态变量,从所有角色的位置开始,他们往往不断移动.如果不跟踪变化的价值,你怎么能做有用的事情呢？
每当我找到讨论这个问题的东西时,它都是用真正技术性的函数来编写的,它假设我没有大量的FP背景.有没有人知道一种方法可以向那些对命令式编码有良好,扎实理解的人解释这一点,但是谁在功能方面是完整的n00b？
编辑:到目前为止,一堆回复似乎试图让我相信不可变值的优点.我得到那个部分.这很有道理.我不明白的是,如何在没有可变变量的情况下跟踪必须改变和不断变化的值.
或者,如果你玩视频游戏,有很多状态变量,从所有角色的位置开始,他们往往不断移动.如果不跟踪变化的价值,你怎么能做有用的事情呢？
如果您有兴趣,这里有一系列用Erlang描述游戏编程的文章.
您可能不会喜欢这个答案,但在使用它之前,您将无法获得功能性程序.我可以发布代码示例并说"在这里,你不看 " - 但如果你不理解语法和基本原则,那么你的眼睛只是茫然.从你的角度来看,它看起来好像我在做命令式语言一样,但只是设置各种边界来有目的地使编程变得更加困难.我的观点是,你只是在经历Blub悖论.
起初我很怀疑,但几年前我跳上了功能编程火车,并爱上了它.函数式编程的技巧是能够识别模式,特定的变量赋值,并将命令状态移动到堆栈.例如,for循环变为递归:
// Imperative
let printTo x =
for a in 1 .. x do
printfn "%i" a
// Recursive
let printTo x =
let rec loop a = if a <= x then printfn "%i" a; loop (a + 1)
loop 1
它不是很漂亮,但我们得到了同样的效果,没有突变.当然,只要有可能,我们都希望完全避免循环并将其抽象出来:
// Preferred
let printTo x = seq { 1 .. x } |> Seq.iter (fun a -> printfn "%i" a)
Seq.iter方法将枚举整个集合并为每个项目调用匿名函数.非常便利 :)
我知道,打印数字并不令人印象深刻.但是,我们可以对游戏使用相同的方法:保持堆栈中的所有状态,并使用递归调用中的更改创建新对象.通过这种方式,每个帧都是游戏的无状态快照,其中每个帧只是创建一个全新的对象,其中包含需要更新的无状态对象的所需更改.这个伪代码可能是:
// imperative version
pacman = new pacman(0, 0)
while true
if key = UP then pacman.y++
elif key = DOWN then pacman.y--
elif key = LEFT then pacman.x--
elif key = UP then pacman.x++
render(pacman)
// functional version
let rec loop pacman =
render(pacman)
let x, y = switch(key)
case LEFT: pacman.x - 1, pacman.y
case RIGHT: pacman.x + 1, pacman.y
case UP: pacman.x, pacman.y - 1
case DOWN: pacman.x, pacman.y + 1
loop(new pacman(x, y))
命令性和功能性版本是相同的,但功能版本显然不使用可变状态.功能代码保持所有状态保持在堆栈上 - 这种方法的好处是,如果出现问题,调试很容易,您只需要堆栈跟踪.
这可以扩展到游戏中的任意数量的对象,因为所有对象(或相关对象的集合)都可以在自己的线程中呈现.
几乎我能想到的每个用户应用程序都将状态作为核心概念.
在函数式语言中,我们只是返回一个包含我们想要的更改的新对象,而不是改变对象的状态.它比听起来更有效率.例如,数据结构很容易表示为不可变数据结构.例如,堆栈非常容易实现:
using System;
namespace ConsoleApplication1
{
static class Stack
{
public static Stack Cons(T hd, Stack tl) { return new Stack(hd, tl); }
public static Stack Append(Stack x, Stack y)
{
return x == null ? y : Cons(x.Head, Append(x.Tail, y));
}
public static void Iter(Stack x, Action f) { if (x != null) { f(x.Head); Iter(x.Tail, f); } }
}
class Stack
{
public readonly T Head;
public readonly Stack Tail;
public Stack(T hd, Stack tl)
{
this.Head = hd;
this.Tail = tl;
}
}
class Program
{
static void Main(string[] args)
{
Stack x = Stack.Cons(1, Stack.Cons(2, Stack.Cons(3, Stack.Cons(4, null))));
Stack y = Stack.Cons(5, Stack.Cons(6, Stack.Cons(7, Stack.Cons(8, null))));
Stack z = Stack.Append(x, y);
Stack.Iter(z, a => Console.WriteLine(a));
Console.ReadKey(true);
}
}
}
上面的代码构造了两个不可变列表,将它们附加在一起以创建一个新列表,并附加结果.在应用程序的任何地方都不使用可变状态.它看起来有点笨重,但这只是因为C#是一种冗长的语言.这是F#中的等效程序:
type 'a stack =
| Cons of 'a * 'a stack
| Nil
let rec append x y =
match x with
| Cons(hd, tl) -> Cons(hd, append tl y)
| Nil -> y
let rec iter f = function
| Cons(hd, tl) -> f(hd); iter f tl
| Nil -> ()
let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
let y = Cons(5, Cons(6, Cons(7, Cons(8, Nil))))
let z = append x y
iter (fun a -> printfn "%i" a) z
创建和操作列表没有必要的可变性.几乎所有数据结构都可以轻松转换为功能等价物.我在这里写了一个页面,它提供了堆栈,队列,左派堆,红黑树,懒惰列表的不可变实现.没有一段代码包含任何可变状态.为了"改变"一棵树,我用我想要的新节点创建了一个全新的树 - 这非常有效,因为我不需要复制树中的每个节点,我可以在我的新节点中重用旧节点树.
使用一个更重要的例子,我也编写了这个完全无状态的SQL解析器(或者至少我的代码是无状态的,我不知道底层的lexing库是否是无状态的).
无状态编程与状态编程一样具有表现力和强大功能,它只需要一些练习来训练自己开始无状态思考.当然,"尽可能无状态编程,必要时进行有状态编程"似乎是大多数不纯函数语言的座右铭.当功能性方法不那么干净或有效时,回避可变性是没有害处的.
简短的回答:你做不到.
那么关于不变性的大惊小怪呢？
如果你精通命令式语言,那么你就知道"全局性很糟糕".为什么？因为它们会在代码中引入(或有可能引入)一些非常难以解决的依赖关系.依赖性并不好; 您希望您的代码是模块化的.程序的一部分不会尽可能少地影响其他部分.和FP为您带来了模块化的圣杯:无副作用,在所有.你只需要你的f(x)= y.把x放进去吧.没有改变x或其他任何东西.FP让你停止思考状态,并开始考虑价值观.您的所有函数都只接收值并生成新值.
这有几个优点.
首先,没有副作用意味着更简单的程序,更容易推理.不用担心引入新的程序部分会干扰并破坏现有的工作部分.
其次,这使得程序可以简单地并行化(有效的并行化是另一回事).
第三,有一些可能的性能优势.假设你有一个功能:
double x = 2 * x
现在你输入的值为3,你得到的值为6.每次.但你也可以做到这一点,对吧？是的.但问题是,在必要时,你可以做得更多.我可以:
int y = 2;
int double(x){ return x * y; }
但我也可以这样做
int y = 2;
int double(x){ return x * (y++); }
命令式编译器不知道我是否会产生副作用,这使得优化更加困难(即双倍2不必每次都是4).功能性的人知道我不会 - 因此,它可以在每次看到"双2"时进行优化.
现在,即使每次创建新值对于计算机内存方面的复杂类型的值而言似乎都非常浪费,但事实并非如此.因为,如果你有f(x)= y,并且值x和y"大部分是相同的"(例如只有几片叶子不同的树)那么x和y可以共享部分内存 - 因为它们都不会变异.
因此,如果这个不可改变的事情是如此伟大,为什么我回答说如果没有可变状态就不能做任何有用的事情.好吧,没有可变性,你的整个程序将是一个巨大的f(x)= y函数.对于程序的所有部分也是如此:只是功能和功能在"纯粹"意义上.正如我所说,这意味着每次都是 f(x)= y .因此,例如readFile("myFile.txt")每次都需要返回相同的字符串值.不太有用.
因此,每个FP都提供了一些改变状态的方法."纯粹的"功能语言(例如Haskell)使用一些可怕的概念(例如monad)来执行此操作,而"不纯"的概念(例如ML)直接允许这样做.
当然,函数式语言还带有许多其他好处,使编程更有效,例如一流的功能等.
请注意,说功能编程没有'状态'有点误导,可能是混乱的原因.它肯定没有"可变状态",但它仍然可以拥有被操纵的值; 它们不能就地更改(例如,您必须从旧值创建新值).
这是一个严重的过度简化,但想象你有一个OO语言,其中类的所有属性只在构造函数中设置一次,所有方法都是静态函数.通过让方法获取包含计算所需的所有值的对象,然后返回带有结果的新对象(甚至可能是同一对象的新实例),您仍然可以执行几乎任何计算.
将现有代码转换为这种范例可能很难,但这是因为它确实需要一种完全不同的思考代码的方式.虽然在大多数情况下你会获得很多免费并行性的机会.
附录:( 关于如何跟踪需要更改的值的编辑)当然,
它们将存储在不可变的数据结构中......
这不是一个建议的"解决方案",但最简单的方法是看到这将始终有效,您可以将这些不可变值存储到地图(字典/散列表)结构中,由"变量名称"键入.
显然,在实际的解决方案中,你会使用一种更理智的方法,但这确实表明,如果没有其他任何工作,最坏的情况你可以通过你的调用树随身携带的这样一个地图"模拟"可变状态.
我觉得有一点误会.纯功能程序具有状态.不同之处在于该状态是如何建模的.在纯函数式编程中,状态由处理某些状态并返回下一状态的函数操纵.然后通过使状态通过一系列纯函数来实现对状态的排序.
甚至全局可变状态也可以这种方式建模.例如,在Haskell中,程序是从世界到世界的功能.也就是说,您传入整个Universe,程序返回一个新的Universe.但实际上,您只需要传入程序实际感兴趣的Universe部分.程序实际上返回一系列动作,作为程序运行的操作环境的指令.
您希望在命令式编程方面看到这一点.好吧,让我们看一下功能语言中一些非常简单的命令式编程.
考虑以下代码:
int x = 1; int y = x + 1; x = x + y; return x;
漂亮的沼泽标准命令式代码.没有做任何有趣的事情,但这可以用于说明.我想你会同意这里有涉及的州.x变量的值随时间而变化.现在,让我们通过发明一种新语法来略微改变符号:
let x = 1 in let y = x + 1 in let z = x + y in z
放括号使它更清楚这意味着什么:
let x = 1 in (let y = x + 1 in (let z = x + y in (z)))
所以你看,state是由一系列纯表达式建模的,这些表达式绑定了下面表达式的自由变量.
您会发现这种模式可以模拟任何类型的状态,甚至是IO.
以下是编写没有可变状态的代码的方法:而不是将更改状态放入可变变量中,而是将其放入函数的参数中.而不是编写循环,你编写递归函数.例如,这个命令式代码:
f_imperative(y) {
local x;
x := e;
while p(x, y) do
x := g(x, y)
return h(x, y)
}
成为这个功能代码(类似Scheme的语法):
(define (f-functional y)
(letrec (
(f-helper (lambda (x y)
(if (p x y)
(f-helper (g x y) y)
(h x y)))))
(f-helper e y)))
或者这个Haskellish代码
f_fun y = h x_final y
where x_initial = e
x_final = loop x_initial
loop x = if p x y then loop (g x y) else x
至于为什么功能性程序员喜欢这样做(你没有问过),你的程序中的更多部分是无状态的,将部分放在一起而没有任何中断的方法就越多.无国籍范式的力量不在于无国籍(或纯洁)本身,而在于它使你能够编写强大的,可重复使用的功能并将它们结合起来的能力.
你可以在John Hughes的论文"功能编程至关重要"中找到一个很好的教程.
这只是做同样事情的不同方式.
考虑一个简单的例子,例如添加数字3,5和10.想象一下这样做,首先通过向它添加5来改变值3,然后将10添加到"3",然后输出当前值" 3"(18).这看起来显然是荒谬的,但它本质上是经常进行基于状态的命令式编程的方式.实际上,你可以拥有许多不同的"3",其价值为3,但却不同.所有这一切看起来都很奇怪,因为我们已经根深蒂固地认识到数字是不可改变的.
现在考虑在将值设为不可变时添加3,5和10.你添加3和5来产生另一个值,8,然后你将10添加到该值以产生另一个值,18.
这些是做同样事情的等效方法.两种方法都存在所有必要的信息,但形式不同.在一个信息中,信息以状态和改变状态的规则存在.另一方面,信息存在于不可变数据和功能定义中.
我讨论的时间已经晚了,但我想为那些正在努力进行函数式编程的人添加几点.
函数式语言与命令式语言保持完全相同的状态更新,但它们通过将更新的状态传递给后续函数调用来实现.这是一个沿着数字线走的简单例子.您的州是您当前的位置.
首先是命令式方法(伪代码)
moveTo(dest, cur):
while (cur != dest):
if (cur < dest):
cur += 1
else:
cur -= 1
return cur
现在的功能方式(伪代码).我非常依赖于三元运算符,因为我希望来自命令背景的人能够实际读取此代码.因此,如果你不使用三元运算符(我总是在我的命令性日子里避免使用它),这就是它的工作原理.
predicate ? if-true-expression : if-false-expression
您可以通过使用新的三元表达式代替false表达式来链接三元表达式
predicate1 ? if-true1-expression : predicate2 ? if-true2-expression : else-expression
所以考虑到这一点,这是功能版本.
moveTo(dest, cur):
return (
cur == dest ? return cur :
cur < dest ? moveTo(dest, cur + 1) :
moveTo(dest, cur - 1)
)
这是一个微不足道的例子.如果这是在游戏世界中移动人们,你必须引入副作用,例如在屏幕上绘制对象的当前位置,并根据对象移动的速度在每次调用中引入一些延迟.但你仍然不需要可变状态.
经验教训是函数式语言通过调用具有不同参数的函数来"改变"状态.显然,这并没有真正改变任何变量,但这就是你得到类似效果的方式.这意味着如果你想进行函数式编程,你将不得不习惯递归思考.
学习递归思考并不难,但它确实需要练习和工具包.那个"学习Java"一书中他们使用递归来计算阶乘的小部分并没有削减它.你需要一个技能工具包,比如通过递归来进行迭代过程(这就是为什么尾递归对函数式语言来说是必不可少的),连续性,不变量等等.如果不了解访问修饰符,接口等,你就不会进行OO编程.同样的事情用于函数式编程.
我的建议是做Little Schemer(注意我说"做"而不是"阅读")然后在SICP做所有的练习.当你完成后,你将拥有与你开始时不同的大脑.
功能编程避免了状态并强调功能.从来没有任何州没有这样的东西,尽管州可能实际上是不可改变的东西,或者融入你正在使用的建筑中.考虑刚刚从文件系统加载文件的静态Web服务器与实现Rubik多维数据集的程序之间的区别.前者将根据旨在将请求转换为文件路径请求的函数实现为来自该文件内容的响应.实际上,除了一小部分配置之外不需要任何状态(文件系统的"状态"实际上超出了程序的范围.无论文件处于什么状态,程序都以相同的方式工作).但是在后者中,您需要为多维数据集和程序实现建模,以便该多维数据集上的操作如何更改其状态.
事实上,即使在没有可变状态的语言中,也可以很容易地获得看起来像可变状态的东西.
考虑具有类型的函数s -> (a, s).从Haskell语法转换,它表示一个函数,它接受一个类型为" s"的参数并返回一对类型为" a"和" s"的值.如果s是我们状态的类型,则此函数采用一种状态并返回一个新状态,并且可能返回一个值(您可以始终返回"unit"aka (),这void在C/C++ 中等同于" ",作为" a"类型).如果你用这样的类型链接几个函数调用(从一个函数返回状态并将它传递给下一个函数),你就有了"可变"状态(实际上你在每个函数中创建一个新状态并放弃旧状态) ).
如果您将可变状态想象为执行程序的"空间",然后考虑时间维度,则可能更容易理解.在时刻t1,"空间"处于特定条件(例如,某些存储器位置具有值5).在稍后的时刻t2,它处于不同的状态(例如,存储器位置现在具有值10).这些时间"切片"中的每一个都是一个状态,它是不可变的(你不能及时回过头来改变它们).所以,从这个角度来看,你是从一个时空箭头(你的可变状态)到一个时空切片(几个不可变状态)的完整时空,你的程序只是将每个切片视为一个值并计算每个切片它们作为应用于前一个的功能.
好吧,也许这不容易理解:-)
将整个程序状态明确表示为一个值似乎是不合适的,必须创建它才能在下一个瞬间(刚创建新的一个之后)被丢弃.对于某些算法,它可能是自然的,但如果不是,则还有另一种技巧.您可以使用虚假状态而不是真实状态,这只是一个标记(让我们称之为伪状态的类型State#).从语言的角度来看,这种假状态存在,并且像任何其他值一样被传递,但编译器在生成机器代码时完全省略了它.它仅用于标记执行顺序.
例如,假设编译器为我们提供了以下功能:
readRef :: Ref a -> State# -> (a, State#) writeRef :: Ref a -> a -> State# -> (a, State#)
从这些类似Haskell的声明转换,readRef接收类似指针或类型为" a" 的值的句柄,以及伪状态,并返回a第一个参数指向的类型" " 的值和新的伪状态.writeRef类似,但改变指向的值.
如果你调用readRef然后传递它返回的伪状态writeRef(可能在中间调用其他不相关的函数;这些状态值创建函数调用的"链"),它将返回写入的值.您可以writeRef使用相同的指针/句柄再次调用它将写入相同的内存位置 - 但是,从概念上它返回一个新的(假的)状态,(假)状态仍然是可变的(一个新的已经"创建" ").如果存在必须计算的实状态变量,编译器将按照它们必须调用的顺序调用函数,但唯一的状态是真实硬件的完整(可变)状态.
(这些谁知道哈斯克尔会注意到我简化了很多东西和中省略一些重要的细节.对于那些谁希望看到更多的细节,看看Control.Monad.State从mtl,并在ST s和IO(又名ST RealWorld)的单子.)
您可能想知道为什么要以这种迂回的方式(而不是简单地在语言中使用可变状态).真正的好处是,你已经物化程序的状态.隐含的内容(您的程序状态是全局的,允许远距离操作等事情)现在是明确的.不接收和返回状态的功能不能修改或受其影响; 他们是"纯粹的".更好的是,你可以拥有单独的状态线程,并且有一些类型魔法,它们可以用于在纯粹的内部嵌入命令式计算,而不会使其不纯(STHaskell中的monad是通常用于此技巧的monad;在State#上面提到的我其实是在GHC的State# s,其实施的使用ST和IO单子).
除了其他人给出的出色答案之外，请考虑类Integer和StringJava。这些类的实例是不可变的，但这并不能使这些类无用，因为它们的实例无法更改。不变性为您提供一些安全性。您知道如果使用String或Integer实例作为a Map的键，则不能更改该键。将此与DateJava中的类进行比较：
Date date = new Date(); mymap.put(date, date.toString()); // Some time later: date.setTime(new Date().getTime());
您已默默地更改了地图中的键！使用不可变对象（例如在函数式编程中）要干净得多。更容易推断出发生了什么副作用-无！这意味着对于程序员来说更容易，对于优化器来说也更容易。
京公网安备 11010802040832号 | 京ICP备19059560号-6 