Извлечение данных из цепочки функций без массивов

Question

Извлечение данных из цепочки функций без массивов

Это сложная тема

Как хранить данные функциональной цепочки Monoidal List?

Я уверен, что мы можем каким-то образом извлечь данные из цепочки функций без использования массива данных. Базовая структура:

L = a => L

очень просто, но эта структура генерирует список:

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

Это может быть связано с Что такое DList?, но эта структура строго зависит только от цепочки функций.

Итак, как вытащить целые значения? Мое нынешнее достижение - просто выдернуть голову и хвост, и я не знаю, как это исправить.

РЕДАКТИРОВАТЬ: я забыл упомянуть, что я пытаюсь сделать, это

List.fold(f) / уменьшить (f)

операция.

Итак, если кто-то выбирает f как Array.concat Это означает, что вы можете извлекать данные в виде массива, но просто сворачивание не ограничивается конкатенацией массива. а также f можно добавить / сумма и т. д.

Итак, в настоящее время, до сих пор, чтобы визуализировать внутреннее поведение, в некотором смысле, я пишу log как f,

EDIT2

Я должен уточнить больше. Спецификация может быть представлена:

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

5

javascript arrays list functional-programming

Источник

19 июл '18 в 08:48

5 ответов

Решение

Довольно серия вопросов у вас здесь. Вот мой взгляд на это:

Мы начинаем с способа построения списков

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 -

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

Дан список типов List a Как мы можем получить значение типа 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 работать с нашим списком acc используя наш новый reduce функция

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 -

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 всегда возвращает лямбду, но этот лямбда имеет тип, который мы не можем определить - иногда он возвращает другую лямбду такого же типа, в других случаях он возвращает совершенно другой результат; в этом случае какое-то число, 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
// ...

4

Источник

user633183 21 июл '18 в 22:41

Я должен признать, что я не прочитал ваши связанные вопросы, и я в основном здесь для забавной головоломки... но помогает ли это в любом случае?

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

Это использует интерфейс, который возвращает объект с concat расширить список и fold запустить редуктор в списке. Опять же, не уверен, что это полный ответ, но он может помочь вам изучить другие направления.

const Empty = Symbol();

const L = (x, y = Empty) => ({
  concat: z => L(z, L(x, y)),
  fold: (f, seed) => f(x, y === Empty ? seed : y.fold(f, seed))
});

const sum = (a, b) => a + b;


console.log(
  L(1)
    .concat(2).concat(3).concat(4).concat(5).concat(6)
    .fold(sum, 0)
)

2

Источник

user3297291 19 июл '18 в 09:28

Работа в процессе

Благодаря потрясающему вкладу @user3297291, я каким-то образом мог реорганизовать код, чтобы он соответствовал моей спецификации, но не работал, потому что я потерял концепцию во время реализации:(

Дело в том, что все должно быть карри, и никакой объект.метод не вовлечен.

Может кто-нибудь "отладить", пожалуйста:)

Начальное значение устанавливается на первый элемент, в этом примере как 1

Я думаю, что это почти сделано.

const isFunction = f => (typeof f === 'function');

const Empty = Symbol();

const L = (x = Empty) => (y = Empty) => z => isFunction(z)
    ? (() => {
        const fold = f => seed => f(x)(y) === Empty
            ? seed
            : (L)(y)(f);
        return fold(z)(x);
    })()
    : L(z)(L(x)(y));


const sum = a => b => a + b;


console.log(
    L(1)(2)(3)(4)(5)(6)(sum)
);

Выход

 z => isFunction(z)
    ? (() => {
        const fold = f => seed => f(x)(y) === Empty
            ? seed
            : (L)(y)(f);
        return fold(z)(x);
    })()
    : L(z)(L(x)(y))

1

Источник

19 июл '18 в 10:46

Я прошел через различные вопросы, которые у вас есть, но я все еще не уверен, что полностью понимаю, что вы ищете. На случай, если вы просто хотите представить связанный список, вот "тупое" представление, в котором не используются хитрые приемы, такие как перегруженные аргументы или значения параметров по умолчанию:

const List = (() => {
  const nil = Symbol()

  // ADT
  const Nil = nil
  const Cons = x => xs => ({ x, xs })
  const match = ({ Nil, Cons }) => l => l === nil ? Nil : Cons(l.x)(l.xs)

  // Functor
  const map = f => match({
    Nil,
    Cons: x => xs => Cons(f(x))(map(f)(xs))
  })

  // Foldable
  const foldr = f => z => match({
    Nil: z,
    Cons: x => xs => f(x)(foldr(f)(z)(xs)) // danger of stack overflow!
                                           // https://wiki.haskell.org/Foldr_Foldl_Foldl%27
  })

  return { Nil, Cons, match, map, foldr }
})()

const { Nil, Cons, match, map, foldr } = List
const toArray = foldr(x => xs => [x, ...xs])([])

const l = Cons(1)(Cons(2)(Cons(3)(Nil)))

const l2 = map(x => x * 2)(l)
const l3 = map(x => x * 3)(l2)

const a = toArray(l3)
console.log(a) // => [6, 12, 18]

0

Источник

user1726343 20 июл '18 в 12:28

Другие вопросы по тегам javascript arrays list functional-programming

user783743 19 июл '18 в 10:57 2018-07-19 10:57 · Accepted Answer · 2018-07-19 10:57

Учитывая выражение как A(a)(b)(f) где f это функция, невозможно знать, f должен быть добавлен в список или это функция сокращения. Следовательно, я собираюсь описать, как писать выражения, как A(a)(b)(f, x) что эквивалентно [a, b].reduce(f, x), Это позволяет нам различать, когда список заканчивается, в зависимости от того, сколько аргументов вы предоставили:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L(k => g((f, a) => k(f, f(a, x))));
    case 2: return g((f, a) => a)(x, a);
    }
};

const A = L(x => x);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

Работает за счет продолжения. Каждый раз, когда мы добавляем новый элемент, мы накапливаем функцию CPS. Каждая функция CPS вызывает предыдущую функцию CPS, тем самым создавая цепочку функций CPS. Когда мы даем этой цепочке функций CPS базовую функцию, она разворачивает цепочку и позволяет нам ее уменьшить. Та же идея стоит за преобразователями и линзами.

Редактировать: решение user633183 является блестящим. Он использует кодирование списков по Церковью, используя правильные сгибы, чтобы облегчить необходимость продолжения, что приводит к более простому коду, который легко понять. Вот ее решение, измененное, чтобы сделать foldr кажется foldl:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L((f, a) => f(g(f, a), x));
    case 2: return g(x, a);
    }
};

const A = L((f, a) => a);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

Вот g церковный список, накопленный до сих пор. Изначально это пустой список. призвание g складывает его справа. Однако мы также строим список справа. Следовательно, похоже, что мы строим список и сворачиваем его слева из-за того, как мы его пишем.

Если все эти функции сбивают вас с толку, то, что действительно делает user633183:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L([x].concat(g));
    case 2: return g.reduceRight(x, a);
    }
};

const A = L([]);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

Как вы можете видеть, она строит список задом наперед, а затем использует reduceRight свернуть список в обратном направлении. Следовательно, похоже, что вы строите и складываете список вперед.