html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Связные списки в функциональном стиле

Рассмотрим вариант реализации связных списков через замыкания.

Для обозначения списков будем использовать нотацию, похожую на Haskell: x:xs, где x — начало списка (head), xs — продолжение (tail).



В качестве языка реализации я выбрал JavaScript.

Конструируем список


Для работы со связными списками необходимы следующие базовые примитивы: nil — пустой список, prepend (cons) — функция вставки в начало списка, head и tail.

Создание списка из двух элементов выглядит следующим образом:

prepend('a', prepend('b', nil))
// 'a' -> 'b' -> nil

Реализация функции prepend:

function prepend(x, xs) {
    return function (select) {
        return select(x, xs)
    }
}

Функция select нужна для доступа к свободным переменным (x:xs).

Реализация head и tail сводится к вызову функции-списка с нужным значением select:

function select_head(x, xs) { return x }
function select_tail(x, xs) { return xs }

function head(a) { return a(select_head) }
function tail(a) { return a(select_tail) }

Осталось реализовать пустой список (nil):

function nil() { return nil }

Таким образом, head(nil) === tail(nil) === nil.

Пример использования


Несложная программа, иллюстрирующая конструирование и обход списка:

var a = prepend('a', prepend('b', nil))
// 'a' -> 'b' -> nil

head(a) // => 'a'
head(tail(a)) // => 'b'
head(tail(tail(a))) // => nil

while (a !== nil) {
    console.log(head(a))
    a = tail(a)
}

Функции высшего порядка


Для получившейся структуры данных можно реализовать функции высшего порядка, например, map:

function map(fn, a) {
    if (a === nil) return nil
    return prepend(fn(head(a)), map(fn, tail(a)))
}

Это позволит работать с нашими списками в функциональном стиле:

var a = prepend(1, prepend(2, prepend(3, nil)))
// 1 -> 2 -> 3 -> nil

function power_of_2(x) { return 1 << x }

var b = map(power_of_2, a)
// 2 -> 4 -> 8 -> nil

Другие ассоциированные функции (filter, reduce) предлагаются читателю в качестве домашнего задания.

Такие дела™


При написании статьи ни один массив не пострадал.

Предвосхищая картинку про троллейбус из хлеба: это, безусловно, не прикладное решение. Более того, на работе за такой коммит могут легко и непринужденно оторвать руки. Что с этим знанием делать дальше — решать вам.

GitHub: github.com/mvasilkov/functional-js
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

0

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции