功能风格(四)


第一类功能二:过滤、减少和更多

在前一篇文章中,我介绍了第一类函数和lambdas的概念,演示了在数组上映射函数的技术,并将其作为显式迭代的替代方法。我接着断言,我们编写的大多数循环要么是为了将一种类型的数组映射到另一种类型的数组,要么是为了从数组中过滤元素,搜索数组中的元素,对它们进行排序,或者累加总数。我答应展示所有这些例子。我最好兑现我的承诺,所以首先,我要以一些古代经典为例。

厄拉多塞的筛子

这是一个寻找素数的算法,由希腊学者厄拉多塞在公元前3世纪发现。这很简单。找出所有质数直到某个数n,以下是你必须做的:

  1. 迭代所有自然数I,其中2 ≤ i ≤ (n ∕ 2)。
  2. 对于每个I,将I的每个倍数m标记为非质数,其中2i ≤ m ≤ n。
  3. 当你完成的时候,所有没有标记的自然数都是质数。

在Java代码中,它应该如下所示:

public class Sieve {

    private Set<Integer> sieve = new HashSet<>();
    private int limit;

    public Sieve(int limit) {
        this.limit = limit;
        for (var n = 2; n <= (limit / 2); n++)
            for (var nonPrime = (n * 2); nonPrime <= limit; nonPrime += n)
                sieve.add(nonPrime);
    }

    public List<Integer> primes() {
        var primes = new ArrayList<Integer>();
        for (var candidate = 1; candidate <= limit; candidate++)
            if (!sieve.contains(candidate))
                primes.add(candidate);
        return primes;
    }
}


构造函数创建筛子,然后创建primes()方法通过筛子有效地“筛选”数字以提取素数。我们可以用它打印出1到10,000之间的所有素数:

public static void main(String[] args) {
    var sieve = new Sieve(10000);
    var primes = sieve.primes();
    for (var prime : primes)
        System.out.print(prime + " ");
    System.out.println();
}


到目前为止,这是当务之急。我选择这个练习作为过滤的例子,因为,毕竟,什么是筛子而不是过滤器?所以,让我们以功能性的方式重写筛子:

public List<Integer> primes() {
    return IntStream.range(1, limit)
            .filter(candidate -> !sieve.contains(candidate))
            .boxed()
            .collect(Collectors.toList());
}


即使IntStream对您来说是新的,希望它的目的是明确的:它给我们一个从1到limit。的.boxed()call将整数流映射到整数流,这样我们就可以将它收集到List在终止操作中。这是因为您不能创建List 关于原语——如果你还记得上一篇文章,Java中的原语有点麻烦。

现在,我们可以收集质数Set 事实上,这可能更合适,因为我们只希望每个质数在输出中出现一次:

public Set<Integer> primes() {
    return IntStream.range(1, limit)
            .filter(candidate -> !sieve.contains(candidate))
            .boxed()
            .collect(Collectors.toSet());
}


但是,这样会产生不良影响,导致结果混乱:

1 2 3 4099 5 2053 7 6151 11 13 2063 4111 17 8209 19 6163 2069 23 8219 [...]


我们也可以通过流式传输和排序结果来解决这个问题:

public static void main(String[] args) {
    var sieve = new Sieve(10000);
    sieve.primes().stream()
            .sorted()
            .forEach(prime -> System.out.print(prime + " "));
    System.out.println();
}


我们可以通过绘制Integers Strings 然后使用Collectors.joining将它们附加在一起,为我们插入空间:

public static void main(String[] args) {
    var sieve = new Sieve(10000);
    System.out.println(sieve.primes().stream()
            .sorted()
            .map(Object::toString)
            .collect(Collectors.joining(" ")));
}


也许,在这里,你可以开始看到功能性风格的吸引力。只需声明你想发生的事情,并让语言为你安排——不用再担心fencepost错误!这个代码的前一个版本在每个数字后面都附加了一个空格,如果它不应该对你来说很重要的话,修复它将会非常困难。在这可能对你有所帮助之前,你已经经历过多少种情况?我去过那里很多次了。

我真的想强调这一点。这就是程序员的省力之处。这不是人们几十年来梦想的那种省力方式——当机器为你编写程序时,人们用某种自然语言表达他们的愿望。这个梦被误导的原因是语法从来都不是编程中最难的部分。编程总是分析一个问题,并把它明确地编码,这样它就可以被机器执行。功能性风格不会改变这一点。相反,功能风格帮助你解决已经解决的问题,例如将这些字符串附加在一起,同时在它们之间插入空格。你不应该每次都写代码来做这些事情。

关闭

够了。如果我们重写sieve()像这样的方法:

public Set<Integer> primes() {
    return IntStream.range(1, limit)
            .boxed()
            .filter(notInNonPrimesUpTo(limit))
            .collect(Collectors.toSet());
}


这是怎么回事?那notInNonPrimesUpTo(int)方法返回一个Predicate,它是一个接受单个参数并返回布尔值的函数:

private Predicate<Integer> notInNonPrimesUpTo(int limit) {
    var sieve = new HashSet<Integer>();
    for (var n = 2; n <= (limit / 2); n++)
        for (var nonPrime = (n * 2); nonPrime <= limit; nonPrime += n)
            sieve.add(nonPrime);
    return candidate -> !sieve.contains(candidate);
}


因此,它构建了一个筛子,并返回一个测试候选人是否在筛子中的λ。这不是非常低效吗?它不会在每次测试一个候选人的时候制造筛子吗?事实并非如此——它只会制造一次筛子。当filter()方法在流上被调用,它调用notInNonPrimesUpTo一次,返回lambda谓词。它是为流中的每个元素执行的lambda。这个λ也是一个关闭。纯lambda函数只依赖于它的输入参数,而闭包也可以访问它所创建的范围内的变量,在这种情况下,就是sieve集合。尽管notInNonPrimesUpTo方法已退出,则sieveset保持在范围内,因为lambda已经“关闭”了它。只要lambda本身保持在作用域内,它关闭的资源将保持可用,并且不会被垃圾收集器回收。

酷。我们走得有点太远了

那么筛子本身的产生呢,也可以用一条小溪来完成吗?是的。

private Predicate<Integer> notInNonPrimesUpTo(int limit) {
    Set<Integer> sieve = IntStream.range(2, (limit / 2))
            .boxed()
            .flatMap(n -> Stream.iterate(n * 2, nonPrime -> nonPrime += n)
                    .takeWhile(nonPrime -> nonPrime <= limit))
            .collect(Collectors.toSet());
    return candidate -> !sieve.contains(candidate);
}


我不认为我真的会在Java中这样做。对我来说,这段代码似乎比命令式版本更难理解。仅仅因为你能做一件事并不意味着你应该做。

Stream.iterate部分是有趣的,但是解释它将会超越我们自己,所以我将在后面的文章中回到这一点。这flatMap值得解释一下。我们这里有一个函数被映射到一个数组上,这个数组本身返回一个数组,所以[2,3,4,5 …]是这样映射的:

  • 2 → [4,6,8,10,12 …]
  • 3 → [6,9,12,15,18 …]
  • 4 → [8,12,16,20,24 …]
  • 5 → [10,15,20,25,30 …]
  • ...

但是,我们不想要数组的数组;我们想把它展平成一维阵列。那是什么flatMap对我们来说是这样,相反,我们得到:

[4,6,8,10,12 … 6,9,12,15,18 … 8,12,16,20,24 … 10,15,20,25,30 …]

最后,Collectors.toSet()为我们剔除重复的。这就是我们的筛子。

聚合操作

如果你浏览了Java streams API或LINQ,如果你是一个. NET开发人员,你会看到几个其他的基于搜索的操作:查找任何,首先查找,任何匹配,等等。它们都是基于谓词的,工作方式基本上与过滤相同,所以我不会详述它们。相反,我想现在将我们的注意力转向聚合操作。回想一下,在本系列的早期,我们有一个计算阶乘的递归程序,如下所示:

public static int factorial(int number) {
    if (number == 1)
        return number;
    else
        return number * (factorial(number - 1));
}


这个算法属于“计算累积结果的循环”的范畴,这是我承诺不用循环也能完成的另一种情况。我们在Java中通过使用reduce。为了计算n的阶乘,首先,我们需要得到一个从1到n的整数流。

IntStream.iterate(1, n -> n += 1)
        .takeWhile(n -> n <= 10)
        .forEach(System.out::println);


通常,数学家反过来定义阶乘,即向下计数:

5!= 5 × 4 × 3 × 2 × 1

无论我们向上还是向下计数,结果都是一样的,所以我们最好向上计数,因为这样更简单。为了计算阶乘,我们使用reduce作为流的终止操作:

public static int factorial(int number) {
    return IntStream.iterate(1, n -> n += 1)
            .takeWhile(n -> n <= number)
            .reduce(1, (acc, next) -> acc * next);
}


reduce方法接受两个参数,它们是:

  • 一个标识值(1)
  • 为流中的每个元素执行的lambda,它本身有两个参数:
    • 一个参数接收当前流元素的值。
    • 另一个在第一次迭代中接收相同的值,并且在每次后续迭代中,它接收前一次计算的结果。

的最终结果reduce方法是lambda函数对流中最后一个元素的结果。如果您想知道lambda参数的走向,文档说明函数必须是关联的,所以这并不重要。无论标识值是什么,它都必须满足这样的条件:当它与任何其他值一起传递给累加器函数时,其他值作为结果返回。用数学术语来说,同一性是这样定义的:

f(x,恒等式)= x

对于乘法和除法,恒等式的值是单位。而对于加法和减法,它是零。

在C#中,该操作称为Aggregate不是减少,而是相反,它基本上是相同的:

public static int Factorial(int number)
{
    return Enumerable.Range(1, number)
            .Aggregate(1, (acc, next) => acc * next);
}


机器人之爱

但是不要认为减少仅限于计算算术总数。您可以将一种类型元素的数组简化为完全不同类型的结果。为了说明这一点,让我们使用另一个我们喜欢在Codurance使用的编程练习,我们称之为火星漫游者。

我们正在模拟机器人漫游车。它的“世界”是一个整数坐标网格,它可以指向四个基本方向中的任何一个:北、东、南或西。漫游者可以左转,可以右转,也可以前进。它是用一系列指令编程的,比如LAARA也就是说:左,前,前,右,前。

在Clojure中,我们可以定义一个制造机器人的函数:

(defn robot [coordinates bearing]
  (hash-map :coordinates coordinates, :bearing bearing))


这样做是为了创建一个机器人给我们一个简单的数据结构来表示机器人的状态,如下所示:

user=> (robot {:x -2 :y 1} :east)
{:coordinates {:x -2, :y 1}, :bearing :east}


在Clojure中,哈希映射文本由包含多个键值对的花括号定义,例如{:key1 value1 :key2 value2 ...}。以冒号为前缀的名称(例如:east)仅仅是符号;他们只代表他们自己。它们不需要被声明,因为除了它们的名字,它们没有任何价值。符号可以比较,即(= :foo :foo)是真的(= :foo :bar)是假的,这使得它们便于地图键和其他用途。

现在,为了能够转动,我们需要知道向左或向右转动的效果,这取决于我们机器人的方位。因此,让我们构建一个数据结构来保存循环:

(def rotations
  {:north {:left :west, :right :east}
   :east {:left :north, :right :south}
   :south {:left :east, :right :west}
   :west {:left :south, :right :north}})


这告诉我们,当我们的机器人指向四个方向中的任何一个时,向左或向右转动后,它的新方位会是什么。使用它,我们可以定义一个函数来使机器人右转:

(defn turn-right [robot]
  (let [bearing (:bearing robot)]
    (assoc robot :bearing (-> rotations bearing :right))))


这三行代码中有相当多的内容。为了帮助您理解它,首先要知道的是,您可以从给定键的映射中获取值,如下所示:

user=> (def a-map {:key1 "value 1" :key2 "value 2"})
#'user/a-map
user=> (:key1 a-map)
"value 1"
user=> (:key2 a-map)
"value 2"


就是这样(:bearing robot)获取机器人的当前方位。这->符号被称为“线程优先”宏;这是…的简写(:right (bearing rotations))或者,换句话说,它获得与机器人当前方位相对应的旋转,然后是向右旋转后的新方位。“线程优先”和“线程最后”宏是Clojure对Lisp表单末尾出现的紧密连接的回答,有些人觉得这种语言令人反感。它们还允许以从左到右的顺序编写复合函数,有些人可能会觉得这更自然(我就是这么认为的)。

assoc函数的行为就像它在映射中添加或替换键值对一样。在这种情况下,它似乎更新了机器人的方位。当然,Clojure中的所有数据结构都是不可变的,那么它做什么呢事实上创建一个新的地图,同时保持原始地图不变。

向左转动机器人的功能是相似的,当然,如果我们想这样做的话,我们可以提取共同的功能:

(defn turn-left [robot]
  (let [bearing (:bearing robot)]
    (assoc robot :bearing (-> rotations bearing :left))))


我们可以轻松测试REPL的转弯功能:

user=> (turn-left (robot {:x 0 :y 0} :north))
{:coordinates {:x 0, :y 0}, :bearing :west}

user=> (turn-left (robot {:x 0 :y 0} :west))
{:coordinates {:x 0, :y 0}, :bearing :south}

user=> (turn-left (robot {:x 0 :y 0} :south))
{:coordinates {:x 0, :y 0}, :bearing :east}

user=> (turn-left (robot {:x 0 :y 0} :east))
{:coordinates {:x 0, :y 0}, :bearing :north}

user=> (turn-right (robot {:x 0 :y 0} :north))
{:coordinates {:x 0, :y 0}, :bearing :east}

user=> (turn-right (robot {:x 0 :y 0} :east))
{:coordinates {:x 0, :y 0}, :bearing :south}

user=> (turn-right (robot {:x 0 :y 0} :south))
{:coordinates {:x 0, :y 0}, :bearing :west}

user=> (turn-right (robot {:x 0 :y 0} :west))
{:coordinates {:x 0, :y 0}, :bearing :north}


请注意,它从不改变坐标,只改变方位。这给了我们一个可以当场转身的机器人。为了移动,我们还需要知道向前移动对它的位置的影响,根据它的方位:

(def translations
  {:north {:delta-x 0, :delta-y 1}
   :east {:delta-x 1, :delta-y 0}
   :south {:delta-x 0, :delta-y -1}
   :west {:delta-x -1, :delta-y 0}})


现在,我们可以编写一个函数,让机器人沿着当前方位向前移动:

(defn move-ahead [robot]
  (let [{ {x :x, y :y} :coordinates, bearing :bearing} robot]
    (let [{delta-x :delta-x, delta-y :delta-y} (translations bearing)]
      (assoc robot :coordinates {:x (+ x delta-x), :y (+ y delta-y)}))))


那里正在进行一些稍微复杂的破坏,但希望已经足够清楚了。我们从机器人那里得到坐标和方位,然后进一步把坐标分解成x和y分量。然后,我们根据机器人的方位查找要应用的平移。最后,我们返回一个新的机器人,它的方位与原来的机器人相同,其坐标为(x+δx,y+δy)。我们可以再次在REPL测试这一功能:

user=> (move-ahead (robot {:x 0 :y 0} :north))
{:coordinates {:x 0, :y 1}, :bearing :north}

user=> (move-ahead (robot {:x 0 :y 0} :east))
{:coordinates {:x 1, :y 0}, :bearing :east}

user=> (move-ahead (robot {:x 0 :y 0} :south))
{:coordinates {:x 0, :y -1}, :bearing :south}

user=> (move-ahead (robot {:x 0 :y 0} :west))
{:coordinates {:x -1, :y 0}, :bearing :west}


最后,我们需要能够处理一系列指令并确定最终的机器人状态。为此,我们需要一个能够解码指令并将相关功能应用于机器人的功能:

(defn do-step [robot next-step]
  (case next-step
    \A (move-ahead robot)
    \L (turn-left robot)
    \R (turn-right robot)))


然后,这是一个简单的事情,迭代指令序列,跟踪机器人的状态,并调用do-step获取下一个机器人状态的每条指令:

(defn simulate [steps initial-robot]
  (loop [remaining-steps steps, robot initial-robot]
    (if (empty? remaining-steps)
      robot
      (recur (rest remaining-steps) (do-step robot (first remaining-steps))))))


因此...?

但是等等!这只是另一个计算累积结果的循环。它是可还原的,好像你没有猜到。当然,你做到了。所以,这也能起作用:

(defn simulate [steps initial-robot]
  (reduce do-step initial-robot steps))


嗯,当然,我听到你说,“但那只是时髦的魔法克洛伊,对不对?”不是这样!你可以在C#中做完全相同的事情:

private readonly Dictionary<Bearing, Rotation> _rotations = new Dictionary<Bearing,Rotation>
{
    {Bearing.North, new Rotation(Bearing.West, Bearing.East)},
    {Bearing.East, new Rotation(Bearing.North, Bearing.South)},
    {Bearing.South, new Rotation(Bearing.East, Bearing.West)},
    {Bearing.West, new Rotation(Bearing.South, Bearing.North)}
};

private readonly Dictionary<Bearing, Coordinates> _translations = new Dictionary<Bearing, Coordinates>
{
    {Bearing.North, new Coordinates(0, 1)},
    {Bearing.East, new Coordinates(1, 0)},
    {Bearing.South, new Coordinates(0, -1)},
    {Bearing.West, new Coordinates(-1, 0)}
};

private Robot TurnLeft(Robot robot)
{
    var rotation = _rotations[robot.Bearing];
    return new Robot(robot.Coordinates, rotation.Left);
}

private Robot TurnRight(Robot robot)
{
    var rotation = _rotations[robot.Bearing];
    return new Robot(robot.Coordinates, rotation.Right);
}

private Robot MoveAhead(Robot robot)
{
    var delta = _translations[robot.Bearing];
    return new Robot(
        new Coordinates(
        robot.Coordinates.X + delta.X,
        robot.Coordinates.Y + delta.Y), 
        robot.Bearing);
}

private Robot DoStep(Robot robot, char nextStep)
{
    switch (nextStep)
    {
        case 'L': return TurnLeft(robot);
        case 'R': return TurnRight(robot);
        default: return MoveAhead(robot);
    }
}


驱动机器人的命令代码可能是:

public Robot Simulate(string instructions, Robot initialRobot)
{
    var robot = initialRobot;
    foreach (var step in instructions)
        robot = DoStep(robot, step);
    return robot;
}


但是,我们可以毫不犹豫地做到:

public Robot Simulate(string instructions, Robot initialRobot)
{
    return instructions.Aggregate(
        initialRobot, 
        (robot, step) => DoStep(robot, step));
}


MapReduce

我不应该在结束的时候不提这个,因为你几乎肯定听过这个术语。这是一种“大数据”技术,和函数式编程一样,是当今最流行的话题之一。在最后两集里,我们研究了被称为“映射”和“减少”的技术,所以你可以相当合理地推断出你现在知道如何做了MapReduce 管用。然而,它稍微复杂一些。MapReduce 在三四个常规处理步骤中处理数据,尽管它们看起来都很熟悉。我们称之为MapReduce,因为FilterMapShuffleReduce 没有相同的戒指:

  1. 过滤数据集(如有必要),只获取您感兴趣的记录。
  2. 通过对每个记录应用一些函数来转换数据集(“映射”步骤)。
  3. 将转换后的数据集中的记录分组在一起。这有时被称为“洗牌”步骤,但是其他的解释,比如MongoDB文档,把这个操作和映射步骤混在一起。分组的工作方式是为每条记录计算一些身份值,并将这些值用作hashmap中的键。每个键都与一组记录相关联,这些记录共享同一个键。
  4. 通过对每个数组应用与上述相同的缩减函数,向下聚合转换后的数据集(“缩减”步骤)。的最终结果MapReduce 操作是一组键值对。

如果你一直在密切关注这一系列的最后两集,那么你现在就知道如何做到这一切。所以,一定要完善你的简历,去找一份高薪的数据科学家工作吧!

下次

希望到目前为止,我已经开始让你相信循环是一个只有在你真正需要的时候才应该达到的构造,而在大多数情况下,你并不需要。LINQ、Streams和其他现代语言中的类似特性可以为您实现许多这样的用例,而打字和管理工作要少得多。正如我们在上一篇文章开头看到的排序示例一样,这些语言可以处理已经解决的部分问题:如何有效地对数组进行排序、搜索项目、删除重复项、按特定键分组等。你可以自由地专注于你的问题领域特有的方面。因此,代码中的信噪比得到了提高,使其更清晰、更容易理解,并且不太可能隐藏错误。

在最后两篇文章中,我们已经对一级函数进行了相当彻底的研究。下一次,我们将介绍一个密切相关的概念——高阶函数。我们还将研究函数的组成,我将尝试解释可怕的单子模式。事实上,我希望我不仅能帮助你理解它,还能让你相信它的实用性。

这篇文章首次发表在Condurance博客。