时间戳

首页 > 解决方案 > 从没有数组的函数链中提取数据

javascript - 从没有数组的函数链中提取数据

问题描述

这是一个高级话题

Monoidal List的功能链如何存储数据？

我很确定我们可以以某种方式从函数链中提取数据，而无需使用存储数据的数组。基本结构是：

L = a => L

很简单，但是这个结构会生成一个列表：

L(1)(2)(3)(4)(5)(6)()

这可能与 什么是 DList？ ，但这种结构严格依赖于函数链。

那么，提取整个值的方法是什么？我目前的成就只是把头和尾巴都拔了出来，我不知道如何解决这个问题。

编辑：我忘了提到我想做的是

List.fold(f) / reduce(f)

手术。

因此，如果选择fasArray.concat这意味着您可以将数据提取为数组，但简单的折叠并不限于数组连接。并且f可以加/和等。

所以，目前，到目前为止，为了可视化内部行为，在某种意义上，我写log为f.

编辑2

我必须进一步澄清。规范可以呈现：

const f = (a) => (b) => a + b;//binary operation

A(a)(b)(f) = f(a)(b)  // a + b

A(a)(b)(c)(f) = f(f(a)(b))(c) // a + b + c

所以这正是

(a b c).reduce(f)

事情，以及何时

f = (a) => (b) => a.concat(b)

结果将是[a, b, c]。

Array.concat只是广义二元运算的一员f。

起初，这个挑战对我的技能来说很容易，但结果却很难，我觉得最好问问更聪明的编码员。

谢谢。

const A = a => {

    const B = b => (b === undefined)
        ? (() => {
            log("a " + a);
            return A();
        })()
        : c => (c === undefined)
            ? (() => {
                log("b " + b);
                return B()();
            })()
            : B;

    return B;

};
 

A(1)(2)(3)(4)(5)(6)()

function log(m)  {
    console.log((m)); //IO
    return m;
};

结果：

b 6
a 1
a undefined

标签： javascriptarrayslistfunctional-programming

解决方案

您在这里遇到的一系列问题。这是我的看法：

我们从一种构造列表的方法开始

  • nil是一个表示空列表的常量
  • cons (x, list)构造一个x添加到前面的新列表list

// nil : List a
const nil =
  (c, n) => n

// cons : (a, List a) -> List a
const cons = (x, y = nil) =>
  (c, n) => c (y (c, n), x)

// list : List Number
const myList = 
  cons (1, cons (2, cons (3, cons (4, nil))))

console.log (myList ((x, y) => x + y, 0))
// 10

为了满足您的高尔夫球可变参数咖喱界面，这里是autoCons

const autoCons = (init, n) => 
{ const loop = acc => (x, n) =>
    isFunction (x)
      ? acc (x, n)
      : loop (cons (x, acc))
  return loop (nil) (init, n)
}

const isFunction = f =>
  f != null && f.constructor === Function && f.length === 2

const nil =
  (c, n) => n

const cons = (x, y = nil) =>
  (c, n) => c (y (c, n), x)

console.log
  ( autoCons (1) ((x,y) => x + y, 0)             // 1
  , autoCons (1) (2) ((x,y) => x + y, 0)         // 3
  , autoCons (1) (2) (3) ((x,y) => x + y, 0)     // 6
  , autoCons (1) (2) (3) (4) ((x,y) => x + y, 0) // 10
  )

我们的编码使编写其他通用列表函数成为可能，例如isNil

// isNil : List a -> Bool
const isNil = l =>
  l ((acc, _) => false, true)

console.log
  ( isNil (autoCons (1))     // false
  , isNil (autoCons (1) (2)) // false
  , isNil (nil)              // true
  )

或者喜欢length

// length : List a -> Int
const length = l =>
  l ((acc, _) => acc + 1, 0)

console.log
  ( length (nil)                  // 0
  , length (autoCons (1))         // 1
  , length (autoCons (1) (2))     // 2
  , length (autoCons (1) (2) (3)) // 3
  )

或者nth获取列表中的第 n 个项目

// nth : Int -> List a -> a
const nth = n => l =>
  l ( ([ i, res ], x) =>
        i === n
          ? [ i + 1, x ]
          : [ i + 1, res]
    , [ 0, undefined ]
    ) [1]

console.log
  ( nth (0) (autoCons ("A") ("B") ("C")) // "A"
  , nth (1) (autoCons ("A") ("B") ("C")) // "B"
  , nth (2) (autoCons ("A") ("B") ("C")) // "C"
  , nth (3) (autoCons ("A") ("B") ("C")) // undefined
  )

我们可以为我们的列表实现类似map和的功能filter

// map : (a -> b) -> List a -> List b
const map = f => l =>
  l ( (acc, x) => cons (f (x), acc)
    , nil
    )

// filter : (a -> Bool) -> List a -> List a
const filter = f => l =>
  l ( (acc, x) => f (x) ? cons (x, acc) : acc
    , nil
    )

我们甚至可以使用我们的列表制作一个程序，该程序将列表作为参数

// rcomp : (a -> b) -> (b -> c) -> a -> c
const rcomp = (f, g) =>
  x => g (f (x))

// main : List String -> String   
const main = letters =>
  autoCons (map (x => x + x))
           (filter (x => x !== "dd"))
           (map (x => x.toUpperCase()))
           (rcomp, x => x)
           (letters)
           ((x, y) => x + y, "")

main (autoCons ("a") ("b") ("c") ("d") ("e"))
// AABBCCEE

在下面的浏览器中运行程序

const nil =
  (c, n) => n

const cons = (x, y = nil) =>
  (c, n) => c (y (c, n), x)

const isFunction = f =>
  f != null && f.constructor === Function && f.length === 2

const autoCons = (init, n) => 
{ const loop = acc => (x, n) =>
    isFunction (x)
      ? acc (x, n)
      : loop (cons (x, acc))
  return loop (nil) (init, n)
}

const map = f => l =>
  l ( (acc, x) => cons (f (x), acc)
    , nil
    )

const filter = f => l =>
  l ( (acc, x) => f (x) ? cons (x, acc) : acc
    , nil
    )

const rcomp = (f, g) =>
  x => g (f (x))

const main = letters =>
  autoCons (map (x => x + x))
           (filter (x => x !== "dd"))
           (map (x => x.toUpperCase()))
           (rcomp, x => x)
           (letters)
           ((x, y) => x + y, "")

console.log (main (autoCons ("a") ("b") ("c") ("d") ("e")))
// AABBCCEE

对不起这是我的错

让我们回顾一下我们最初的List例子

// list : List Number
const myList = 
  cons (1, cons (2, cons (3, cons (4, nil))))

console.log
  ( myList ((x, y) => x + y, 0) // 10
  )

我们将其概念化myList为数字列表，但我们通过myList (...)像函数一样调用而自相矛盾。

这是我的错。在尝试简化示例时，我跨越了抽象的障碍。我们来看看和的类型nil—— cons</p> 

// nil : List a
// cons : (a, List a) -> List a

给定一个 type 列表List a，我们如何得到一个 type 的值a呢？myList在上面的例子（下面重复）中，我们通过作为函数调用来作弊。这是只有实施者应该知道nil的内部知识cons

// myList is a list, not a function... this is confusing...
console.log
  ( myList ((x, y) => x + y, 0) // 10
  )

如果你回顾一下我们最初的实现List，

// nil : List a
const nil =
  (c, n) => n

// cons : (a, List a) -> List a
const cons = (x, y = nil) =>
  (c, n) => c (y (c, n), x)

我还欺骗了您提供简化的类型注释，例如List a. 究竟是List什么？

我们将解决所有这些问题，并从我们的实施开始List

List, 取 2

下面nil并cons具有完全相同的实现。我只修复了类型注释。最重要的是，我添加reduce了一种从列表容器中“取出”值的方法。

的类型注释List更新为List a r——这可以理解为“一个包含类型值的列表a，当减少时，将产生一个类型的值r。” 

// type List a r = (r, a) -> r

// nil : List a r
const nil =
  (c, n) => n

// cons : (a, List a r) -> List a r
const cons = (x, y = nil) =>
  (c, n) => c (y (c, n), x)

// reduce : ((r, a) -> r, r) -> List a -> r
const reduce = (f, init) => l =>
  l (f, init)

现在我们可以保持List一个理智的类型，并将你想要的所有不稳定的行为推入autoCons函数中。下面我们更新以使用我们的新功能autoCons处理我们的列表accreduce

const autoCons = (init, n) => 
{ const loop = acc => (x, n) =>
    isFunction (x)
      // don't break the abstraction barrier
      ? acc (x, n)
      // extract the value using our appropriate list module function
      ? reduce (x, n) (acc)
      : loop (cons (x, acc))
  return loop (nil) (init, n)
}

所以说到类型，让我们来看看autoCons——</p> 

autoCons (1)                  // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2)              // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3)          // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3) (add, 0) // 6

嗯autoCons，总是返回一个 lambda，但是那个 lambda 有一个我们无法确定的类型——有时它返回另一个相同类型的 lambda，有时它返回一个完全不同的结果；在这种情况下，一些数字，6

因此，我们不能轻易地将autoCons表达式与程序的其他部分混合和组合。如果你放弃这个不正常的驱动来创建可变参数柯里化接口，你可以创建一个autoCons可类型化的接口

// autoCons : (...a) -> List a r
const autoCons = (...xs) =>
{ const loop = (acc, x = nil, ...xs) =>
    x === nil
      ? acc
      : loop (cons (x, acc), ...xs)
  return loop (nil, ...xs)
}

因为autoCons现在返回一个已知的List（而不是由可变参数柯里化引起的神秘未知类型），我们可以将一个autoCons列表插入到我们List模块提供的各种其他函数中。

const c =
  autoCons (1, 2, 3)

const d =
  autoCons (4, 5, 6)

console.log
  ( toArray (c)                         // [ 1, 2, 3 ]
  , toArray (map (x => x * x) (d))      // [ 16, 25, 36 ]
  , toArray (filter (x => x != 5) (d))  // [ 4, 6 ]
  , toArray (append (c, d))             // [ 1, 2, 3, 4, 5, 6 ]
  )

当autoCons返回我们无法依赖的类型时，这种混合和组合表达式是不可能的。另一个需要注意的重要事情是该List模块为我们提供了扩展其功能的地方。我们可以很容易地添加上面使用的函数，比如map, filter, append, 和toArray– 当你试图通过可变参数柯里化接口推动一切时，你会失去这种灵活性

现在让我们看看List模块中的这些添加 - 正如您所看到的，每个函数都是类型良好的并且具有我们可以依赖的行为

// type List a r = (r, a) -> r

// nil : List a r
// cons : (a, List a r) -> List a r
// reduce : ((r, a) -> r, r) -> List a r -> r

// length : List a r -> Int
const length =
  reduce
    ( (acc, _) => acc + 1
    , 0
    )

// map : (a -> b) -> List a r -> List b r
const map = f =>
  reduce
    ( (acc, x) => cons (f (x), acc)
    , nil
    )

// filter : (a -> Bool) -> List a r -> List a r
const filter = f =>
  reduce
    ( (acc,x) =>  f (x) ? cons (x, acc) : acc
    , nil
    )

// append : (List a r, List a r) -> List a r
const append = (l1, l2) =>
  (c, n) =>
    l2 (c, l1 (c, n))

// toArray : List a r -> Array a
const toArray =
  reduce
    ( (acc, x) => [ ...acc, x ]
    , []
    )

现在作为我们模块的一部分甚至autoCons是有意义的

// autoCons : (...a) -> List a r
const autoCons = (...xs) =>
{ const loop = (acc, x = nil, ...xs) =>
    x === nil
      ? acc
      : loop (cons (x, acc), ...xs)
  return loop (nil, ...xs)
}

向List模块添加任何其他功能

// nth: Int -> List a r -> a
// isNil : List a r -> Bool
// first : List a r -> a
// rest : List a r -> List a r
// ...

推荐阅读