Функциональное построение списка из пар - PullRequest
Новая
       87

Функциональное построение списка из пар

1 голос
/ 30 мая 2020

Я пытаюсь построить список из примитивных данных Pair (см. реализацию для полной реализации). Функция-конструктор использует рекурсию, и по этой причине на нее влияет ограничение пространства стека. Одно из возможных решений - передать (массив, убывающий индекс массива, инкрементный список) и сохранить состояние как часть рекурсивного вызова, но это по-прежнему использует пространство во время выполнения.

Есть ли способ реализовать эту хвостовую рекурсию? Я запускаю это в Node. 

// listIter::[xs] -> List[xs]
export function listIter(xs) {
    const construct = (list, index) => {
        return (index === -1) ?
            list :
            construct(pair(xs[index], list), index - 1);
    }

    return construct(Pair.empty(), xs.length - 1);
}

1 Ответ

2 голосов
/ 30 мая 2020

SICP - замечательный текст. Код здесь должен быть достаточно понятным. На данный момент у меня мало времени, но я свяжусь с ним позже сегодня, чтобы добавить некоторые детали и ответить на возможные последующие вопросы -

main. js

// main.js
import { of, fromArray, toString } from './list'

toString(of(999))
// 999->Empty.

toString(fromArray([]))
// Empty.

toString(fromArray([1]))
// 1->Empty.

toString(fromArray([1,2,3,4]))
// 1->2->3->4->Empty.

const big =
  Array.from(Array(100000), (_, x) => x)

toString(fromArray(big))
// 0->1->2->3->...99999->Empty.

список. js

import { loop, recur } from './function'

const empty =                      // <-- empty list
  Symbol()                         // <-- any sentinel value

const pair = (left, right) =>      // <-- pair constructor
  ({ pair, left, right })          // <-- plain object

const of = (x = null) =>           // <-- "of" constructor
  pair(x, empty)                   // <-- singleton list

const fromArray = (xs = []) =>
  loop                             // <-- begin loop
    ( ( r = empty                  // <-- init r
      , i = 0                      // <-- init i
      ) =>                         // <-- loop body
        i >= xs.length             // <-- exit condition
          ? reverse(r)             // <-- tail; return
          : recur                  // <-- tail; recur
              ( pair(xs[i], r)     // <-- next r
              , i + 1              // <-- next i
              )
    )

const reverse = (node = empty) =>
  loop                             // <-- begin loop
    ( ( r = empty                  // <-- init r
      , t = node                   // <-- init t
      ) =>                         // <-- loop body
        t === empty                // <-- exit condition
          ? r                      // <-- tail; return
          : recur                  // <-- tail; recur
              ( pair(t.left, r)    // <-- next r
              , t.right            // <-- next t
              )
    )

const toString = (node = empty) =>
  loop                             // <-- begin loop
    ( ( r = "Empty."               // <-- init r
      , t = reverse(node)          // <-- init t
      ) =>                         // <-- loop body
      t === empty                  // <-- exit condition
        ? r                        // <-- tail; return
        : recur                    // <-- tail; recur
            ( t.left + "->" + r    // <-- next r
            , t.right              // <-- next t
            )
    )

// "pair" is not exported
// it is an implementation detail of our list module
export { empty, of, fromArray, reverse, toString }

функция. js

const identity = x => x

const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })

const loop = (f = identity, ...init) =>
  whileTrue               // <-- functional while
    ( r => r && r.recur   // <-- while condition
    , r => f(...r)        // <-- next r
    , f(...init)          // <-- init r
    )

const whileTrue = (test = identity, next = identity, r = null) =>
{ while(Boolean(test(r))) // <-- while test(r) is true
    r = next(r)           // <-- nexr r
  return r                // <-- return r
}

export { identity, loop, recur, whileTrue }

демо

Разверните фрагмент ниже, чтобы проверить результат в своем браузере - 

// function.js -------
const identity = x => x

const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })

const loop = (f = identity, ...init) =>
  whileTrue
    ( r => r && r.recur
    , r => f(...r)
    , f(...init)
    )

const whileTrue = (test = identity, next = identity, r = null) =>
{ while(Boolean(test(r)))
    r = next(r)
  return r
}

// list.js -------
const empty =
  Symbol()

const pair = (left, right) =>
  ({ pair, left, right })

const of = (x = null) =>
  pair(x, empty)

const fromArray = (xs = []) =>
  loop
    ( ( r = empty
      , i = 0
      ) =>
        i >= xs.length
          ? reverse(r)
          : recur
              ( pair(xs[i], r)
              , i + 1
              )
    )

const reverse = (node = empty) =>
  loop
    ( ( r = empty
      , t = node
      ) =>
        t === empty
          ? r
          : recur
              ( pair(t.left, r)
              , t.right
              )
    )

const toString = (node = empty) =>
  loop
    ( ( r = "Empty."
      , t = reverse(node)
      ) =>
      t === empty
        ? r
        : recur
            ( t.left + "->" + r
            , t.right
            )
    )

// main.js -------
console.log(toString(of(999)))
// 999->Empty.

console.log(toString(fromArray([])))
// Empty.

console.log(toString(fromArray([1])))
// 1->Empty.

console.log(toString(fromArray([1,2,3,4])))
// 1->2->3->4->Empty.

const big =
  Array.from(Array(100000), (_, x) => x)

console.log(toString(fromArray(big)))
// 0->1->2->3->...99999->Empty.

дальнейшая абстракция

Если бы раньше было больше времени, я бы, наверное, написал pair как отдельный модуль - 

// pair.js
import { raise } from './function'

const empty =
  Symbol()

const pair = (left, right) =>
  ({ pair, left, right })

const left = (t = empty) =>
  t === empty
    ? raise(`cannot read value from empty`)
    : t.left

const right = (t = empty) =>
  t === empty
    ? raise(`cannot read value from empty`)
    : t.right

const of = ([ left, right ]) =>
  pair(left, right)

export { empty, pair, left, right, of }

Добавление raise в function модуль - 

// function.js
const identity = //

const recur = //

const loop = //

const whileTrue = //

const raise = (msg = "") => // functional throw
  { throw Error(msg) }

export { identity, loop, recur, whileTrue, raise }

Создание лучшего барьера абстракции между list модулем и pair модулем - 

// list.js
import { loop, recur } from './function'
import { empty, pair, left, right } from './pair'

const of = (x = null) =>
  pair(x, empty)                   // <-- pair, empty

const fromArray = (xs = []) =>
  loop
    ( ( r = empty                  // <-- empty
      , i = 0
      ) =>
        i >= xs.length
          ? reverse(r)
          : recur
              ( pair(xs[i], r)     // <-- pair
              , i + 1              //
              )
    )

const reverse = (node = empty) =>
  loop
    ( ( r = empty                  // <-- empty
      , t = node
      ) =>
        t === empty                // <-- empty
          ? r
          : recur
              ( pair(left(t), r)   // <-- pair, left
              , right(t)           // <-- right
              )
    )

const toString = (node = empty) =>
  loop
    ( ( r = "Empty."
      , t = reverse(node)
      ) =>
      t === empty                  // <-- empty
        ? r
        : recur
            ( left(t) + "->" + r   // <-- left
            , right(t)             // <-- right
            )
    )

// re-export empty
// it's okay that List.empty and Pair.empty are
// represented using the same sentinel value
export { empty, of, fromArray, reverse, toString }

Приятно видеть запись pair как отдельный шаг, потому что это показывает нам, как разбивать модули, когда структуры данных становятся слишком запутанными.

...