如何使用Clojure以函数式方式解决这个编程问题?

3

我有一个编程问题,在Ruby中我知道如何解决,但不知道在Clojure中最好的方法是什么(我认为可能有一种优雅的方式以函数式思维来解决这个问题)。

问题可以简化为:


我有一个3升的水桶,里面装满了水。桶底有一个洞,每秒漏10毫升水(即需要300秒/5分钟才能排空)。我有一杯容量为100毫升的水,我可以用它向桶里倒入新水。

我只能将整杯水倒入桶中,不能部分倒入。倒水是瞬间完成的。

制定一组时间步骤,我可以在这些时间步骤中向桶中倒水。


我知道使用代数学方法可以很容易地解决这个问题,但实际问题涉及到随时间变化的“泄漏速率”和不总是等于100毫升的“新玻璃容积”,因此不能简单地通过一个公式来解决。

在Ruby中解决这个问题的方法是使用“Bucket实例”跟踪桶的容积,并在许多时间步骤上测试桶是否有100毫升的空间。如果有,就倒掉杯子里的水,并将水加入“Bucket实例”中。继续时间步骤,观察桶的容积。

我希望我所描述的清楚明白。


你能提示一下为什么答案不总是290毫升吗? - Leon Grapenthin
@LeonGrapenthin 请查看问题描述后的段落。 - Brandon
2个回答

5

函数式编程最重要的概念之一是,任何没有外部副作用的变异都可以转移到不可变函数参数绑定中。

在这里,模拟的时间和桶的水位是主要的函数参数,并且它们会在每个递归调用中更新。其他参数被建模为时间的函数。我们可以将每个这样的函数想象成实际上是基于时间增量的延迟序列,就像fill-times函数本身一样。或者是由向量查找建模的分段线性方程,或者是其他类似的方式。

user> 
(defn fill-times
  [time level
   {:keys [sample-rate calc-bucket-size calc-leak-rate calc-glass-size]
    :as params}]
  (loop [t time l level]
    (let [input-capacity (calc-glass-size time)
          bucket-capacity (calc-bucket-size time)
          has-room (> (- bucket-capacity l) input-capacity)
          leak-delta (* (calc-leak-rate) sample-rate -1)]
      (if has-room
        (lazy-seq (cons t (fill-times t (+ l input-capacity)
                                      params)))
        (recur (+ t sample-rate) (+ l leak-delta))))))

#'user/fill-times
user> (take 50 (fill-times 0 0 {:sample-rate 1
                                 :calc-bucket-size (constantly 3000)
                                 :calc-leak-rate (constantly 10)
                                 :calc-glass-size (constantly 100)}))
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201)

当有足够的空间时,玻璃杯就被倒掉(当然也会立即再次被填满),我们记下了时间,并调用函数获取下一次的时间。当没有足够的空间时,我们进行递归,更新时间和桶的水位。结果是一个(理论上无限的)懒惰序列,其中包含可以倒出玻璃杯的时间(假设玻璃杯会立即被填满和倒掉)。

所有内容都是无单位的,但是当然你的输入单位必须一致。 - noisesmith
我真希望我能给这个赞两次。1)你为我的问题提供了一个完全合理的解决方案。2)你教会了我一个非常重要的概念,即函数式编程。我在想,当我试图以函数式的方式解决问题时,将数据输入的变异视为不可变参数这种思维方式是否是我大脑一直无法克服的问题所在。 - Brandon
有没有地方可以更深入地了解这个概念(以及其他类似的概念,因为我只是一个业余的面向对象编程爱好者,可能不知道一些相关的知识)? - Brandon
Clojure的作者Rich Hickey有许多录制的演讲,其中涉及到这个问题(以及通过显式地记录时间来消除可变性的相关概念)。http://www.infoq.com/author/Rich-Hickey。此外,任何一本像《Programming Clojure》、《Clojure Programming》以及在线书籍《Clojure from the Ground Up》(http://aphyr.com/posts/301-clojure-from-the-ground-up-welcome)和《Clojure for the Brave and True》(http://www.braveclojure.com/)这样的不错的Clojure书都会处理这些问题。 - noisesmith
1
小提示-泄漏增量逻辑是错误的,我刚刚更新了它(只有在时间增加时才应用泄漏)。 - noisesmith

3

我对Clojure没有太多经验,但可以这样理解:它是一个按时间步长延迟计算状态值的懒序列。从上一个状态值中惰性地计算出每个状态值。

这是一个递归方程或差分方程。它根据上一个值计算新值,而不会覆盖它们。

状态值可以仅为桶水平或一个元组,其中包含(时间、桶水平、倒入次数)。


1
谢谢你向我介绍递归方程!我之前不知道这个概念。实际上,我找到了另一个 Stack Overflow 的问题,其中有人提出了 Clojure 的递归方程的一般形式。 - Brandon

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