在函数式编程中时间函数是如何存在的?

我必须承认我对函数式编程了解不多。我从这里和那里读到它,所以开始知道在函数式编程中,一个函数返回相同的输出,对于相同的输入,无论函数被调用多少次。它就像一个数学函数,对于函数表达式中包含的输入参数的相同值,计算出相同的输出。

例如,考虑这个:

f(x,y) = x*x + y; // It is a mathematical function

无论您使用f(10,4)多少次,它的值始终是104。因此,无论您在哪里编写了f(10,4),都可以将其替换为104,而不改变整个表达式的值。这个属性被称为表达式的引用透明性

正如维基百科所说(链接),

相反,在函数式代码中,函数的输出值只取决于函数的输入参数,因此调用函数f两次,参数x的值相同,两次将产生相同的结果f(x)。

函数式编程中是否存在时间函数(返回当前的时间)?

  • 如果是,那它怎么可能存在?它是否违反了函数式编程的原则?它特别违反了引用透明性,这是函数式编程的属性之一(如果我理解正确的话)。

  • 如果没有,那么在函数式编程中如何知道当前时间呢?

58083 次浏览

是也不是。

不同的函数式编程语言解决这些问题的方法不同。

在Haskell(一个非常纯粹的Haskell)中,所有这些事情都必须发生在被称为I / O单子的东西中——参见在这里

你可以把它看作是将另一个输入(和输出)输入到你的函数(世界状态)中,或者更简单地认为是“不确定性”发生的地方,比如得到变化的时间。

像f#这样的其他语言只是内置了一些不纯性,所以你可以有一个函数为相同的输入返回不同的值——就像正常的命令式语言一样。

正如Jeffrey Burka在他的评论中提到的: 这里是I/O单子很好的介绍直接来自Haskell的维基

大多数函数式编程语言都不是纯粹的,也就是说,它们允许函数不仅依赖于它们的值。在这些语言中,完全有可能有一个返回当前时间的函数。从你标记这个问题的语言中,这适用于Scalaf#(以及毫升的大多数其他变体)。

在像Haskell清洁这样的纯语言中,情况是不同的。在Haskell中,当前时间不是通过函数,而是通过所谓的IO操作,这是Haskell封装副作用的方式。

在Clean中,它将是一个函数,但该函数将以一个世界值作为参数,并返回一个新的世界值(除了当前时间)作为结果。类型系统将确保每个世界值只能使用一次(并且每个消耗世界值的函数将产生一个新的世界值)。这样,每次调用time函数时都必须使用不同的参数,因此允许每次返回不同的时间。

是的,函数式编程中可以存在一个获得时间的函数,它使用了函数式编程的一个稍微修改过的版本,称为非纯函数式编程(默认的或主要的是纯函数式编程)。

在获取时间(或读取文件,或发射导弹)的情况下,代码需要与外部世界进行交互以完成工作,而这个外部世界并不是基于函数式编程的纯粹基础。为了允许纯函数式编程世界与这个不纯的外部世界进行交互,人们引入了不纯函数式编程。毕竟,不与外部世界交互的软件除了做一些数学计算之外没有任何用处。

很少有函数式编程语言具有这种内嵌的不纯特性,这样就不容易区分哪些代码是不纯的,哪些是纯的(如f#等),而一些函数式编程语言确保当你做一些不纯的事情时,代码与纯代码相比明显突出,如Haskell。

另一种有趣的方式是,函数式编程中的get time函数将接受一个“world”对象,该对象具有世界的当前状态,如时间、生活在世界中的人数等。然后从世界对象中获取时间,这个世界对象总是纯的,即你在相同的世界状态下通过,你将总是得到相同的时间。

在Haskell中,使用一个名为单孢体的构造来处理副作用。单子基本上意味着你将值封装到容器中,并在容器中使用一些函数将值与值之间的函数链接起来。如果容器的类型为:

data IO a = IO (RealWorld -> (a,RealWorld))

我们可以安全地实现IO动作。IO类型的动作是一个函数,它接受RealWorld类型的令牌,并返回一个新令牌和结果。

这背后的想法是,每个IO操作都会改变外部状态,由神奇的标记RealWorld表示。通过使用单子,我们可以将多个函数链接在一起,从而改变现实世界。单子最重要的功能是>>=,发音为绑定:

(>>=) :: IO a -> (a -> IO b) -> IO b

>>=使用一个操作和一个函数,该函数使用该操作的结果并由此创建一个新操作。返回类型是新动作。例如,假设有一个函数now :: IO String,它返回一个表示当前时间的String。我们可以用函数putStrLn链接它来打印它:

now >>= putStrLn

或者用# eyz0符号写,这对命令式程序员来说更熟悉:

do currTime <- now
putStrLn currTime

所有这些都是纯粹的,因为我们将关于外部世界的突变和信息映射到RealWorld令牌。因此,每次运行此操作,当然都会得到不同的输出,但输入是不相同的:RealWorld令牌是不同的。

另一种解释是:没有函数可以获得当前时间(因为它一直在变化),但是行动可以获得当前时间。让我们说getClockTime是一个常数(或者一个零函数,如果你喜欢),它表示获得当前时间的行动。这个行动无论什么时候使用都是一样的,所以它是一个真正的常数。

同样地,让我们说print是一个函数,它需要一些时间来表示并将其打印到控制台。由于函数调用在纯函数式语言中不会产生副作用,因此我们将其想象为一个接受时间戳并返回将其打印到控制台的行动的函数。同样,这是一个真实的函数,因为如果您给它相同的时间戳,它将每次打印时返回相同的行动

现在,如何将当前时间打印到控制台?你必须把这两个动作结合起来。我们怎么做呢?我们不能只是将getClockTime传递给print,因为print需要一个时间戳,而不是一个动作。但是我们可以想象有一个操作符,>>=,它有两个动作,一个获取时间戳,一个将时间戳作为参数并输出。将此应用于前面提到的操作,结果是……tadaaa……一个获取当前时间并打印它的新动作。这恰好是在Haskell中实现的。

Prelude> System.Time.getClockTime >>= print
Fri Sep  2 01:13:23 東京 (標準時) 2011

因此,从概念上讲,您可以这样看待它:纯函数式程序不执行任何I/O,它定义了一个行动,然后运行时系统执行它。行动每次都是相同的,但是执行它的结果取决于执行它时的环境。

我不知道这是否比其他解释更清楚,但它有时会帮助我这样思考。

“当前时间”不是一个函数。它是一个参数。如果您的代码依赖于当前时间,这意味着您的代码是由时间参数化的。

是的!你说对了!Now()或CurrentTime()或任何这种风格的方法签名都没有以某种方式显示引用透明性。但是通过对编译器的指令,它是由系统时钟输入参数化的。

通过输出,Now()可能看起来没有遵循引用透明性。但是系统时钟和它上面的功能的实际行为是坚持的 引用透明性。< / p >

这完全可以用纯功能的方式来完成。有几种方法可以做到这一点,但最简单的是让time函数不仅返回时间,还返回必须调用以获取下一次时间测量的函数

在c#中,你可以这样实现它:

// Exposes mutable time as immutable time (poorly, to illustrate by example)
// Although the insides are mutable, the exposed surface is immutable.
public class ClockStamp {
public static readonly ClockStamp ProgramStartTime = new ClockStamp();
public readonly DateTime Time;
private ClockStamp _next;


private ClockStamp() {
this.Time = DateTime.Now;
}
public ClockStamp NextMeasurement() {
if (this._next == null) this._next = new ClockStamp();
return this._next;
}
}

(请记住,这是一个简单的示例,而不是实际的示例。特别是,列表节点不能被垃圾收集,因为它们是由ProgramStartTime根的。)

这个“ClockStamp”类就像一个不可变的链表,但实际上节点是按需生成的,所以它们可以包含“当前”时间。任何想要测量时间的函数都应该有一个'clockStamp'参数,并且必须在其结果中返回其最近的时间测量值(这样调用者就不会看到旧的测量值),如下所示:

// Immutable. A result accompanied by a clockstamp
public struct TimeStampedValue<T> {
public readonly ClockStamp Time;
public readonly T Value;
public TimeStampedValue(ClockStamp time, T value) {
this.Time = time;
this.Value = value;
}
}


// Times an empty loop.
public static TimeStampedValue<TimeSpan> TimeALoop(ClockStamp lastMeasurement) {
var start = lastMeasurement.NextMeasurement();
for (var i = 0; i < 10000000; i++) {
}
var end = start.NextMeasurement();
var duration = end.Time - start.Time;
return new TimeStampedValue<TimeSpan>(end, duration);
}


public static void Main(String[] args) {
var clock = ClockStamp.ProgramStartTime;
var r = TimeALoop(clock);
var duration = r.Value; //the result
clock = r.Time; //must now use returned clock, to avoid seeing old measurements
}

当然,这有点不方便,必须把最后的测量输入输出,输入输出,输入输出。隐藏样板文件的方法有很多,尤其是在语言设计级别。我认为Haskell使用这种技巧,然后通过使用单子隐藏丑陋的部分。

你的问题合并了计算机语言的两种相关衡量标准:函数式/命令式和纯粹/不纯粹。

函数式语言定义了函数的输入和输出之间的关系,命令式语言按照特定的执行顺序描述了特定的操作。

纯粹的语言不会产生或依赖副作用,而不纯粹的语言则自始至终都在使用副作用。

百分之百纯粹的程序基本上是无用的。他们可能会进行有趣的计算,但因为他们没有副作用,他们没有输入或输出,所以你永远不会知道他们计算了什么。

要想有用,一个程序至少要有一点不纯。使纯程序有用的一种方法是将它放在一个薄的非纯包装器中。比如下面这个未经测试的Haskell程序:

-- this is a pure function, written in functional style.
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)


-- This is an impure wrapper around the pure function, written in imperative style
-- It depends on inputs and produces outputs.
main = do
putStrLn "Please enter the input parameter"
inputStr <- readLine
putStrLn "Starting time:"
getCurrentTime >>= print
let inputInt = read inputStr    -- this line is pure
let result = fib inputInt       -- this is also pure
putStrLn "Result:"
print result
putStrLn "Ending time:"
getCurrentTime >>= print

是的,对于一个纯函数来说返回时间是可能的,如果它把时间作为一个参数。不同的时间论据,不同的时间结果。然后形成其他时间函数,并将它们与函数(时间)转换(高阶)函数的简单词汇表结合起来。由于该方法是无状态的,因此这里的时间可以是连续的(与分辨率无关),而不是离散的。这种直觉是函数式响应式编程(FRP)的基础。

我很惊讶,没有一个答案或评论提到共代数或共归纳。通常,同归纳法在对无限数据结构进行推理时被提及,但它也适用于无穷无尽的观察流,例如CPU上的时间寄存器。一个协代数模型隐藏状态;和共归纳模型观察状态。(正常诱导模型构建状态。)

这是响应式函数式编程中的一个热门话题。如果你对这类东西感兴趣,请阅读这个:http://digitalcommons.ohsu.edu/csetech/91/(28页)

  • # EYZ0 (# EYZ1)

如果是,那么它怎么可能存在?这难道不违反原则吗 函数式编程吗?它尤其违反了参照原则 透明度< / p >

它的存在不是纯粹的功能性的。

或者如果没有,那么如何知道当前时间在函数中 编程吗?< / p >

首先,了解如何在计算机上检索时间可能是有用的。从本质上讲,有一个板载电路来记录时间(这就是电脑通常需要一个小电池的原因)。然后可能会有一些内部进程在某个内存寄存器上设置时间的值。这本质上可以归结为CPU可以检索到的值。


对于Haskell,有一个“IO动作”的概念,它表示一种类型,可以执行一些IO进程。因此,我们引用的不是time值,而是IO Time值。所有这些都是纯功能性的。我们不是在引用time,而是在引用'读取时间寄存器的值'

当我们实际执行Haskell程序时,IO操作将实际发生。

您正在讨论函数式编程中一个非常重要的主题,即执行I/O。许多语言的实现方式是使用嵌入式领域特定语言,例如,一种子语言,其任务是编码行动,这可以产生结果。

例如,Haskell运行时希望我定义一个名为main的操作,该操作由组成程序的所有操作组成。运行时然后执行此操作。大多数情况下,这样做只会执行纯代码。运行时将不时使用计算出的数据执行I/O,并将数据反馈回纯代码。

您可能会抱怨这听起来像作弊,在某种程度上确实如此:通过定义动作并期望运行时执行它们,程序员可以做普通程序可以做的所有事情。但是Haskell的强类型系统在程序的纯部分和“不纯”部分之间创建了一个强大的障碍:你不能简单地在当前CPU时间上增加2秒并打印它,你必须定义一个导致当前CPU时间的操作,并将结果传递给另一个增加2秒并打印结果的操作。编写太多的程序被认为是糟糕的风格,因为与Haskell类型相比,它会告诉我们一切,我们可以知道值是什么,因为它很难推断造成了哪些效果。

示例:C中的clock_t c = time(NULL); printf("%d\n", c + 2);和Haskell中的main = getCPUTime >>= \c -> print (c + 2*1000*1000*1000*1000)。操作符>>=用于组合操作,将第一个操作的结果传递给产生第二个操作的函数。这看起来很神秘,Haskell编译器支持语法糖,允许我们编写后面的代码如下:

type Clock = Integer -- To make it more similar to the C code


-- An action that returns nothing, but might do something
main :: IO ()
main = do
-- An action that returns an Integer, which we view as CPU Clock values
c <- getCPUTime :: IO Clock
-- An action that prints data, but returns nothing
print (c + 2*1000*1000*1000*1000) :: IO ()

后者看起来很有必要,不是吗?

在函数式编程中时间函数是如何存在的?

早在1988年,Dave Harrison在定义带有实时处理功能的早期函数式语言时就面临着这个问题。他为露丝选择的解决方案可以在他的论文函数式实时编程:Ruth语言及其语义的第50页找到:

一个唯一的时钟在运行时自动提供给每个Ruth进程,以提供实时信息,[…]

那么这些时钟是如何定义的呢?第61页:

时钟树由一个表示当前时间的非负整数节点和两个包含未来事件时间的子树组成。

此外:

当树被(惰性地)计算时,每个节点都用系统时间在节点实例化的时候的值进行实例化,从而使程序引用当前时间。

翻译成Haskell:

type Clock = Tree Time
type Time  = Integer -- must be zero or larger


data Tree a = Node { contents :: a,
left     :: Tree a,
right    :: Tree a }

除了访问当前时间(使用contents),每个Ruth进程还可以提供其他时钟(使用leftright),以便在程序的其他地方使用。如果一个进程不止一次需要当前时间,那么它必须每次都使用一个新节点——实例化后,节点的内容保持不变。

这就是函数式语言中时间函数的存在方式:无论调用它的地方,它总是应用于唯一的输入值(在这里是一个时间树)。

不引入计划生育的其他概念就可以回答这个问题。

可能性1:time作为函数参数

一门语言包括

  1. 语言核心和
  2. 标准库。

引用透明性是语言核心的属性,而不是标准库。它绝不是用那种语言编写的程序的属性。

使用OP的符号,应该有一个函数

f(t) = t*v0 + x0; // mathematical function that knows current time

他们会要求标准库获取当前时间,例如1.23,并以该值作为参数f(1.23)(或者只是1.23*v0 + x0,引用透明!)来计算函数。这样代码就能知道当前时间。

可能性2:返回值为时间

回答OP的问题:

函数式编程中是否存在时间函数(返回当前时间)?

是的,但是这个函数必须有一个参数,你必须用不同的输入来计算它,这样它就会返回不同的当前时间,否则它就违反了FP的原则。

f(s) = t(s)*v0 + x0; // mathematical function t(s) returns current time

这是我上面所描述的另一种方法。但话又说回来,首先获取这些不同的输入 s的问题仍然取决于标准库。

可能性3:函数式响应式编程

其思想是函数t()与函数t2配对计算当前时间。当一个需要当前时间的时候,他们会调用t2(),然后它会给出函数t3,等等

(x, t2) = t(); // it's x o'clock now
...
(x2, t3) = t2(); // now it's already x2 o'clock
...
t(); x; // both evaluate to the initial time, referential transparency!

关于FP还有更多,但我认为这超出了op的范围。例如,如何要求标准库计算一个函数,并以纯函数的方式对其返回值进行操作:这是关于副作用而不是参考透明度的。