Logo

菜单

发布于 2026-01-06 6 阅读
0

仅使用函数组合器创建链表 什么是函数组合器？ 放弃结构化链接 链接列表 计数列表 映射列表 过滤 但函数组合器真的有用吗？ 总结

仅使用函数组合器创建链表

什么是函数组合器？

废弃结构

链接该列表

清点一下那份清单

地图列表

筛选

但函数组合器真的有用吗？

概括

黑板上写着ABC

Object今天我将演示如何不使用任何数据结构（例如数组或数组）来创建链表Arrays；而是使用函数组合器。

我假设您已经熟悉链表是什么。如果您需要复习一下链表，请查看@aspittel的《thank u, next: an introduction to linked lists》。

我的目标是向你展示一些你可能从未见过的东西，比如柯里化、部分应用、闭包和函数组合子能实现哪些功能。最重要的是，希望你在学习的过程中也能感受到乐趣。

⚠️ 本文嵌入了 Runkit。您可以运行、修改、调整和体验本页上的示例。

什么是函数组合器？

功能性思维中的定义：组合子

“组合子”一词用来描述那些结果仅取决于其参数的函数。这意味着它不依赖于外部世界，尤其不能访问任何其他函数或全局值。

实际上，这意味着组合器函数只能以各种方式组合其参数。

信息量有点大，或许举些例子会有帮助？

/* ☝️ These are combinators */
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
const B = a => b => c => a (b (c))
//        -    -    -    ---------
//         \   |   /        |
//           arguments   ---
//                      /
//       only arguments are used

/* 👎 These are not */
const nope = a => a.map(double)
//                  --- ------
//                 /           \    
//                /    ⚠️ reaching outside of the func
//               /
//     ⚠️ can't use map either.
const add => a => b => a + b
//                       -
//                      /
// ⚠️ Uh oh, `+` is not part of 'arguments'
Enter fullscreen mode Exit fullscreen mode

总结一下上面的代码：组合器只能使用它的参数。这排除了外部函数、方法和运算符！

别担心，现在还有点困惑也没关系。(⊙_☉)

废弃结构

典型的链表会使用类似这样的数据结构：

class Node {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

/* or */

const node = (data, next) => ({ data, next })

/* or */

const node = (data, next) => [ data, next ]
Enter fullscreen mode Exit fullscreen mode

但我们不会使用任何这些数据结构。我们将使用函数组合器。

在深入探讨组合子池之前，让我们先从一个基本函数开始node：

function node (data, next) {
//             ----  ----
//           /            \
//       our data       the next node
}
Enter fullscreen mode Exit fullscreen mode

那么，我们如何在不使用对象的情况data下访问它呢？如果你说，那就对了！nextnodecallbacks

///////////////////////////////////////////////////////////// // // // 📌 ATTENTION: You can modify and run these code blocks! // // // ///////////////////////////////////////////////////////////// function node (data, next, callback) { return callback(data, next) } // I can use bind to store my data and next values. const head = node.bind(null, 'data', null) // Use a callback to read the values from head. head((data, next) => { return { data, next } })

我不太喜欢这种使用 `.` 的实现方式bind。所以我打算对node函数进行柯里化，这样我就可以使用偏函数来应用 `.`data和 ` next.`。这将达到与使用 `.` 相同的效果，bind但语法要好得多。

const node = data => next => callback => callback (data) (next) // ---- ---- -------- ---- ---- // \ | / / / // parameters are curried ------------- // / // closures make data and next available // to callback when it is finally called. // I can use bind to store my data and next values. const head = node ('data') (null) // ------ ---- // / / // We can partially apply the arguments data and null. // Use a callback to read the values from head. head (data => next => { return { data, next } })

如果你足够仔细，你可能会注意到它node与上面的组合器完全相同V！

所以现在node可以简化为：

const node = V
Enter fullscreen mode Exit fullscreen mode

我们可以像这样创建节点：

const evenOdd = node ('Even') ('Odd')
const leftRight = node ('Left') ('Right')
const yesNo = node ('Yes') ('No')
Enter fullscreen mode Exit fullscreen mode

如果我们分析一下这个部分应用程序的具体操作，它看起来会是这样的：

// first copy the node function
const evenOdd = data => next => callback => callback (data) (next)

// apply 'Even' to data.
const evenOdd =         next => callback => callback ('Even') (next)

// apply 'Odd' to next.
const evenOdd =                 callback => callback ('Even') ('Odd')

// We end up with this:
const evenOdd = callback => callback ('Even') ('Odd')
Enter fullscreen mode Exit fullscreen mode

evenOdd现在它接受一个参数，即 `the` callback。该callback参数需要一个如下所示的函数：

const callback = a => b => { /* ??? */ }
Enter fullscreen mode Exit fullscreen mode

现在我们可以开始玩了。点击play这个运行工具包并修改它callback以返回'Left'。

const V = a => b => c => c (a) (b) const node = V const leftRight = node ('Left') ('Right') // TODO: modify callback so the code returns 'Left' const callback = a => b => {} leftRight (callback) //=> 'Left'

现在再次修改代码以返回'Right'。

太棒了！现在我们来调用'Left'函数data和'Right'函数next。

const data = a => _ => a
const next = _ => b => b
Enter fullscreen mode Exit fullscreen mode

使用我们的新功能重新运行一遍。

const V = a => b => c => c (a) (b) const node = V const data = a => _ => a const next = _ => b => b const leftRight = node ('Left') ('Right') console.log (leftRight (data)) console.log (leftRight (next))

你注意到data它也和我们的一样吗K Combinator？

// 💥 BOOM!
const data = K
Enter fullscreen mode Exit fullscreen mode

next几乎与 相同K Combinator，但略有不同。next返回b，而data返回a。 有个小技巧可以解决这个问题：

// 🧙‍♀️ MAGIC!
const next = K (I)
Enter fullscreen mode Exit fullscreen mode

这个巧妙的技巧启发了我写一整篇文章：《你无法解决的最简单的问题》。我敢打赌，你现在肯定能在2秒钟内解决这个问题！

链接该列表

让我们把学到的知识转换成链表。

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') // Just an Object to detect the end. const first = node ('1st') (Nil) // --- // / // Nil signifies the end const second = node ('2nd') (first) // ----- // / // pass the first node in as the next const third = node ('3rd') (second) // -----_ // / // pass the second node in as the next console.log (third (data)) //=> '3rd' console.log (third (next) (data)) //=> '2nd' console.log (third (next) (next) (data)) //=> '1st'

清点一下那份清单

我们可以创建一个简单的函数来枚举列表并返回计数。

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') const length = (list, value = 0) => list === Nil ? value : length (list (next), value + 1) const first = node ('1st') (Nil) const second = node ('2nd') (first) const third = node ('3rd') (second) console.log (length (first)) //=> 1 console.log (length (second)) //=> 2 console.log (length (third)) //=> 3

地图列表

映射类似于Array。

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') // Don't worry about this implementation. // It is just to demo the code below. const map = func => list => list === Nil ? list : node (func (list (data))) (map (func) (list (next))) const first = node ('1st') (Nil) const second = node ('2nd') (first) const third = node ('3rd') (second) const upper = x => x.toUpperCase() const THIRD = map (upper) (third) console.log (THIRD (data)) //=> '3RD' console.log (THIRD (next) (data)) //=> '2ND' console.log (THIRD (next) (next) (data)) //=> '1ST'

筛选

过滤也类似于Array。

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') // Don't worry about this implementation. // It is just to demo the code below. const filter = predicate => list => list === Nil ? list : predicate (list (data)) ? node (list (data)) (filter (predicate) (list (next))) : filter (predicate) (list (next)) const first = node (1) (Nil) const second = node (2) (first) const third = node (3) (second) const fourth = node (4) (third) const isEven = x => x % 2 === 0 const evens = filter (isEven) (fourth) console.log (evens (data)) //=> 4 console.log (evens (next) (data)) //=> 2

但函数组合器真的有用吗？

当然，你绝对不应该用这种方式创建链表。实际上，你一开始就不应该创建链表。所以，这一切都只是理论上的探讨。

令人惊讶的是，函数组合器也有一些实际用途！

你可能认不出B Combinator

const B = a => b => c => a (b (c))
Enter fullscreen mode Exit fullscreen mode

除非它是这样写的：

const compose = f => g => x => f (g (x))
Enter fullscreen mode Exit fullscreen mode

没错！compose就是B Combinator！如果你好奇的话，pipe就是Q Combinator。

另一个有用的实用函数是`.`。Ramda的库中always有一个这样的函数。你也可以用一个简单的函数组合器来重新创建它。always

const always = K

const awesome = always ('Awesome!')

awesome () //=> 'Awesome!'
awesome (123) //=> 'Awesome!'
awesome ('hello') //=> 'Awesome!'
Enter fullscreen mode Exit fullscreen mode

tap这也是我经常使用的一个常用函数。它可以像这样写（如下所示）。它非常适合管理副作用。

const tap = func => val => {
  func (val) // execute my side effect
  return val // return the original value
}
Enter fullscreen mode Exit fullscreen mode

我们也可以tap这样写：

const tap = S (K)
Enter fullscreen mode Exit fullscreen mode

利用函数组合器可以创造出很多非常有用的东西！

概括

  • 我们学习了如何在不使用任何数据结构的情况下创建链表。
  • 我们学习了什么是函数组合器以及它们有哪些用途。
  • 我们学习了如何使用柯里化、部分应用和闭包来存储数据。

请告诉我你还学到了什么！

请告诉我你对 Runkit 示例的看法。我正在考虑在我的文章中更多地使用它们。

你想了解更多关于函数组合子的知识吗？请在评论区告诉我！

如果你喜欢函数式 JavaScript，请在​​这里或 Twitter 上关注我@joelnet！

干杯!

文章来源：https://dev.to/joelnet/creating-a-linked-list-using-only-function-combinators-5hhk
你应该学习 Redux 吗？Red...
关于招聘开发人员和技术面试流程：消...