Форум 'Декларативное программирование' на RSDN

История функционального программирования

Wed, 13 Aug 2025 13:54:44 GMT

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

Java Interop - один и тот же код возвращает разные значения

Thu, 27 Feb 2025 09:18:08 GMT

Решил тут поиграться с прикручиванием Clojure в Java
Есть такой код:

public class Main {

    public static void main(String[] args) {
        var f1 = Clojure.var("clojure.core", "eval");
        var script =
                """
                        (=
                         "a1b2"
                         (clojure.string/join
                          (map
                           (fn [[a b]] (str a b))
                           (seq ctx))))
                        """;
        f1.invoke(Clojure.read("(defn test [ctx] " + script + ")"));
        var r = Clojure.var("clojure.core", "test")
                .invoke(Map.of("a", 1, "b", 2));

        System.out.println(r);
    }

}

Который на консоль выводит то true, то false
Что я делаю не так?

Заранее благодарен!

Покажите, пожалуйста, профит от функционального программирования.

Sun, 04 Aug 2024 09:57:56 GMT

То есть, два примера консольных программ на Java каждая,
в первом случае когда программа написана в императивном стиле (можно с ООП),
а во втором случае, когда эта же самая программа написана в функциональном стиле (с монадами).

Хочу увидеть, как вторая программа сама задействует многоядерность и обгоняет первую в 28 раз (по числу ядер).

Как работает funcall в Лиспе?

Tue, 02 Jul 2024 04:04:51 GMT

В Common Lisp такой код с функцией funcall:

(print (funcall
        (lambda (x y)
                (format NIL "~d + ~d = ~d" x y (+ x y))
        )
        2
        3
       )
)

И такой без нее:

(print (
        (lambda (x y)
                (format NIL "~d + ~d = ~d" x y (+ x y))
        )
        2
        3
       )
)

Работает совершенно аналогично — вызывает лямбда-выражение с парой параметров и выводит "2 + 3 = 5".

Однако, когда я пытаюсь написать простой пример с ООП:

(setq User-counter 0)
(defun User (name)
    (let
     (
      (id (setq User-counter (+ User-counter 1)))
     )
     (lambda (method)
             (cond
                 ((eq method 'getId) (lambda () id))
                 ((eq method 'getName) (lambda () name))
                 ((eq method 'data) (lambda () (list id name)))
                 ((eq method 'format) (lambda (f) (format NIL f id name)))
             )
     )
    )
)

То вызов методов с funcall работает:

(print (funcall (funcall (User "Worminator") 'format) "id: ~d, name: ~s"))

А вот без funcall выдает ошибку:

(print (((User "Worminator") 'format) "id: ~d, name: ~s"))

EVAL: ((USER "Worminator") 'FORMAT) is not a function name; try using a symbol instead

Почему? Можно ли как-то использовать второй вариант? Что означает not a function name — вообще не понял. И что делает funcall? Зачем нужна apply — ясно, она берет аргументы для вызова из списка, а вот с этой функцией непонятно. В другом диалекте Лиспа, Scheme, кстати, не нашел funcall (или там другое имя для нее).

Как-то запутанно все... В учебнике Святослава Лаврова, по которому когда-то учил Лисп, funcall совершенно не упоминалась, там говорилось, что выражение (f a1 ... aN) просто применяет значение f (которое должно быть лямбдой) к аругментам a1-aN и выдает результат. И вообще весь Лисп описывался 10 базовыми функциями: car, cdr, cons, atom, eq, cond, lambda, defun, setq и quote.

Realworld Example FP

Fri, 26 Nov 2021 02:17:49 GMT

Поделитесь ссылками хороших примеров полноценного приложения на ФЯП типа F#(предпочтительно) или любых других.
Опыта ООП и C# вроде достаточно.
Последнее время есть стойкое ощущение что ФП будущее(или уже настоящее?).
Но учебные статьи в основном сосредоточены на каких-то простых примерах.

Серия видео по теории категорий медленно

Fri, 06 Aug 2021 13:46:43 GMT

https://www.youtube.com/c/RichardSouthwell/playlists
Там есть плейлист Category Theory For Beginners.
Изложение довольно медленное, понятное и подробное (возможно кому-то покажется слишком медленное).
Очень понравилось видео про Universal Properties, наконец-то начал понимать немного.
У автора этих видео еще и книжка есть по теории категорий "Categories and Toposes: Visualized and Explained"
P.S. Не спрашивайте зачем это нужно, just for fun.

Что общего у "carrying" и "lambda calculus"?

Wed, 30 Jun 2021 19:41:15 GMT

Во всех статьях, где описывается что такое каррирование вопрос зачем оно — выносят за рамки статьи.
Приведу цитаты:

Currying provides a way for working with functions that take multiple arguments,
and using them in frameworks where functions might take only one argument.
For example, some analytical techniques can only be applied to functions with a single argument.
Practical functions frequently take more arguments than this.

(какие именно аналитические техники могут быть применены только к функциям одного аргумента?)

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

(и в чём же суть этого усложнения? что за концепция?)

Меня не интересуют "передача коллбеков по-человечески", "оно используется в LINQ", "удобно в Unit-тестировании".

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

Статьи в интернете слишком короткие и не связанные между собой.
Книжки слишком сложные. А учить меня никто не обязан. Как жить?

Youtube-канал F#

Tue, 03 Nov 2020 07:38:14 GMT

Канал F#
Дон Сайм рассказывает принцип работы компилятора. Не плохо смотрится.
Как сказал Дон для тех "кто хочет погрузиться".

F# и уменьшение сложности алгоритма поиска пересечений всех

Mon, 17 Feb 2020 16:19:12 GMT

есть следующая задачка. найти все возможные пересечения в списке, которые содержит в себе "дороги", то есть объекты, состоящие из координат. нарисовал координатную сетку 8х8 и на ней 4 горизонтальные и 3 вертикальные линии. в коде это выглядит как то так

let rh1 =
        road "rh1" [ // дорога содержит имя и список точек
                        point (1., 7., 0.) [BEGIN; COORDINATE]; // точка point (x,y,z) - координата, [] - содержит массив типов точки (не имеет значения в данном случае)
                        point (3., 7., 0.) [COORDINATE];
                        point (5., 7., 0.) [COORDINATE];
                        point (7., 7., 0.) [COORDINATE];
                        point (8., 7., 0.) [COORDINATE; TRAFFICLIGHT; END];
                    ]

    let rh2 =
        road "rh2" [
                        point (1., 5., 0.) [BEGIN; COORDINATE];
                        point (3., 5., 0.) [COORDINATE];
                        point (5., 5., 0.) [COORDINATE];
                        point (7., 5., 0.) [COORDINATE];
                        point (8., 5., 0.) [COORDINATE; TRAFFICLIGHT; END];
                    ]

    let rh3 =
        road "rh3" [
                        point (1., 3., 0.) [BEGIN; COORDINATE];
                        point (3., 3., 0.) [COORDINATE];
                        point (5., 3., 0.) [COORDINATE];
                        point (7., 3., 0.) [COORDINATE];
                        point (8., 3., 0.) [COORDINATE; TRAFFICLIGHT; END];
                    ]

    let rh4 =
        road "rh4" [
                        point (1., 1., 0.) [BEGIN; COORDINATE];
                        point (3., 1., 0.) [COORDINATE];
                        point (5., 1., 0.) [COORDINATE];
                        point (7., 1., 0.) [COORDINATE];
                        point (8., 1., 0.) [COORDINATE; TRAFFICLIGHT; END];
                    ]

    let rv1 =
        road "rv1" [
                        point (3., 8., 0.) [BEGIN; COORDINATE];
                        point (3., 7., 0.) [COORDINATE];
                        point (3., 5., 0.) [COORDINATE];
                        point (3., 3., 0.) [COORDINATE];
                        point (3., 1., 0.) [COORDINATE];
                        point (3., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
                    ]

    let rv2 =
        road "rv2" [
                        point (5., 8., 0.) [BEGIN; COORDINATE];
                        point (5., 7., 0.) [COORDINATE];
                        point (5., 5., 0.) [COORDINATE];
                        point (5., 3., 0.) [COORDINATE];
                        point (5., 1., 0.) [COORDINATE];
                        point (5., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
                    ]

    let rv3 =
        road "rv3" [
                        point (7., 8., 0.) [BEGIN; COORDINATE];
                        point (7., 7., 0.) [COORDINATE];
                        point (7., 5., 0.) [COORDINATE];
                        point (7., 3., 0.) [COORDINATE];
                        point (7., 1., 0.) [COORDINATE];
                        point (7., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
                    ]

далее вызываю соответствующий метод для получения множества всех возможных пересечений (должно быть 12) пересечений

let crossrods = Road.CrossRoads [rh1; rh2; rh3; rh4; rv1; rv2; rv3]

crossrods
|> Seq.iter (fun x -> printfn "position x: %f, y: %f" x.p.x x.p.y)

код алгоритма привожу ниже (весь тип не привожу, только то, что нужно)

let (|Includes|DoesntIncludes|) (point, list) = 
    let tryPoint = List.tryFind (fun c2 ->
                                    if point == c2.p then
                                        true
                                    else
                                        false) list
    match tryPoint with
        | Some(x) -> Includes x
        | _ -> DoesntIncludes

static member CrossRoads2 r1 r2 =

    r1.pl
    |> List.filter (fun c1 -> match (c1.p, r2.pl) with
                                          | Includes(_) -> true
                                          | _ -> false
                               )

static member CrossRoads (roads: Road list) =

    let rec inCross r roads res = 
        match roads with
        | h::t when h.n <> r.n ->
            let nextRes = Seq.append res (Road.CrossRoads2 r h)
            inCross r t nextRes
        | _::t ->
            inCross r t res
        | [] -> res

    roads
        |> Seq.map (fun x -> inCross x roads Seq.empty)
        |> Seq.collect (fun r -> r)
        |> Seq.distinct // это фиксит проблему двойного результата

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

|> Seq.distinct

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

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

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

спасибо

Хвостовая рекурсия при ветвлении в ширь

Fri, 13 Dec 2019 04:13:17 GMT

Попалась головоломка:

type Tree<'a> =
  | Leaf of 'a
  | Branch of 'a * Tree<'a> list


let getInfoList a =
  if System.DateTime.UtcNow.Ticks % 10L > 5L 
  then [ a*2L; a*4L; ]
  else []


let rec buildTree a =
    let lst = getInfoList a
    
    if List.isEmpty lst 
    then
      Leaf (a)
    else
      let subTrees = List.map buildTree lst
      Branch (a, subTrees)


let r = buildTree 1L

buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.

F# и хвостовая рекурсия

Wed, 30 Oct 2019 21:18:06 GMT

имеется двумерный массив, заполненый 1 и 0. по сути — это бинарное изображение, где 0 — это черные пиксели, а 1 — белые. само изображение организовано так, что белые пиксели организованы по группам, которые разделены между собой черными пикселями (стенками).

задача: найти белые пятна на картинке и каждое пятно маркиковать отдельным числом. например, на картинке 3 белых пятна, разделенные черными стенками. то есть в итоговой картинке каждое пятно (состоящее из белых пикселей) обозначено числами 2, 3, 4 и так далее. реализован данный алгоритм так

// Learn more about F# at http://fsharp.org

open System

let source = array2D [[1; 1; 0; 1; 1; 1; 0; 1];
                      [1; 1; 0; 1; 0; 1; 0; 1];
                      [1; 1; 1; 1; 0; 0; 0; 1];
                      [0; 0; 0; 0; 0; 0; 0; 1];
                      [1; 1; 1; 1; 0; 1; 0; 1];
                      [0; 0; 0; 1; 0; 1; 0; 1];
                      [1; 1; 0; 1; 0; 0; 0; 1];
                      [1; 1; 0; 1; 0; 1; 1; 1]]

let (|Value|Zero|Out|) ((x: int), (y: int)) = 
    if x < 0 || y < 0 || x > (source.[0,*].Length - 1) || y > (source.[*,0].Length - 1) then
        Out
    else
        let row = source.[y, *]
        match row.[x] with
            | 0 -> Zero
            | v -> Value(v)

let processSource x y value =

    let rec markBits x y value =
        match (x, y) with
        | Value(v) ->
            if v <> value then
                source.[y, x] <- value
                markBits (x + 1) y value
                markBits (x - 1) y value
                markBits x (y + 1) value
                markBits x (y - 1) value
        | Zero | Out -> ()

    markBits x y value

[<EntryPoint>]
let main argv =
    printfn "Hello World from F#!"

    printfn "origin"
    printfn "%A" source
    printfn "--------------"

    let mutable value = 2

    source
    |> Array2D.iteri (fun y x e -> if e = 1 then
                                        processSource x y value
                                        value <- value + 1)

    printfn "modified"
    printfn "%A" source
    0 // return an integer exit code

результат работы такой

Hello World from F#!
origin
[[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]
--------------
modified
[[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]

по задумке, функция processSource реализована по принцицам хвостовой рекурсии, однако отладчик показывает, что каждый вызов рекурсивной функции markBits добавляет новый кадр в стек. то есть хвостовая рекурсия не работает. не могу понять, почему? ведь задача каждого кадра — всего лишь отметить очередной пиксель нужным числом и вызвать такую же функцию для всех соседних пикселей. сам кадр рекурсии обратно ничего не вычисляет и не возвращает. то есть компилятору нет смысла делать обычную рекурсию.

в чем ошибка? спасибо

Design and Interpretation of Haskell Programs

Wed, 16 Oct 2019 07:40:09 GMT

Похоже Sandy Maguire пишет новую книгу.

But if functional programming is so good, why hasn't it yet taken over the world?

This is a very serious question. If we're right about this, why haven't we won?

F# обращение к элементу кортежа по порядковому номеру

Fri, 20 Sep 2019 12:19:39 GMT

приветствую знатоков F#

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

let (a, b, c, d) = (1, 2, 3, 4)

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

let tuple = (1, 2, 3, 4)
tuple.0 // обращение к первому элементу кортежа
tuple.1 // обращение ко второму элементу кортежа
tuple.2 // обращение к третьем элементу кортежа
tuple.3 // обращение к четвертому элементу кортежа

печально и странно, если подобной возможности в F# нет, хотя она так и напрашивается.

Formality. Новый язык зависимых типов

Sun, 15 Sep 2019 12:50:56 GMT

Formality (см там внизу страницы мультик)

Документация

Что интересного:
Solving the mystery behind Abstract Algorithm’s magical optimizations

Своя версия лямбда исчисления

Towards a simple theorem prover

Can we call a function a googol times?

Своя операционная система Moonad

Okay, nobody reads my Twitter, so I realized I can make random, misguided predictions here and nobody will call me dumb if they don't work out, yet I can tell everyone I was right if they do!

So, here is one: there are many similarities between applying quantum operators to multiple values, and performing computations on highly shared terms of interaction combinators. Conjecture: interaction nets can perform Shor's Algorithm efficiently in classical computers.

Victor Maia

Теги: Affine logic, Self types, SYMMETRIC INTERACTION COMBINATORS, Магия, Cedille, Juvix

P.S. Похоже про interaction net лучше сначала прочитать статью interaction net Lafont
потом Yves Lafont, Interation Combinators, Institut de Mathematiques de Luminy, 1997
и потом A Denotational Semantics for the Symmetric Interaction Combinators Mazza

Elixir, подводные камни, лучшие практики и т.п.

Mon, 05 Aug 2019 10:57:10 GMT

Разыскивается информация по лучшим практикам, подводным камням и т.п. для back-end разработки на Elixir. В принципе, гуглить я умею и восторженных отзывов о том, как всё стало после использования Elixir уже нашел... но а что там плохо? Где и когда все разваливается? Какие практики лучше себя зарекомендовали что бы не развалилось? Поделитесь информацией, пожалуйста

F#, вычисление дистанции между узлами дерева

Mon, 22 Jul 2019 21:29:53 GMT

приветствую. засел за изучение F#. язык и подход для меня новый, все переворачивается с ног на голову, потому прошу помощи. имеется следующий код

module Street

    type Paint =
        | FillColor of float
        | BorderColor of float
        | BorderWidth of float

    type Point =
        | Position of x:float * y:float
        | Description of string
        | Radius of float
        | Lanes of uint32

    type Street =
        | Node of Street * Point list * Street // back * points * right. street like tree
        | Empty

    let distance (pt1: Point) (pt2: Point) =
        let square x = x * x
        sqrt <| square (pt1.x - pt2.x) + square (pt1.y - pt2.y)

смысл следующий. тип Stree — это дорога, представленная в виде дерева. в самом простом случае это дерево имеет вид простого списка, без ответвлений, вот его и рассматриваю.
тип Street хранит в себе узлы (предыдущий, следующий) список типов Point, которые описывают конкретный узел. Point можно рассматривать как некий атрибут, который может принимать следующие типы

Position — координата
Descriptiom — текстовое описание
Radius — радиус
Lanes — количество полос

каждый нод Street может хранить в себе произвольное количество Point

ну суть здесь не в этом. а в том, что получаю ошибку компиляции функции distance

Error FS0039 The field, constructor or member 'x/y' is not defined.

смысл ошибки понятен, но не совсем понятно, как сказать компилятору, что тип Point на самом деле является Position. пробовал разные способы

pt1: Point(x, y)
pt1: Point(x:float, y: float)
pt1: Position
pt1: Position(x, y)

и так далее

может кто подсказать, как заставить компилятор понять, какой тип я передаю в distance?

благодарю

Посоветуйте книгу по Haskell

Tue, 19 Mar 2019 09:45:42 GMT

Давно задумываюсь над изучением какого-нибудь функционального языка, дабы расширить свое сознатие и постичь дзэн. Выбираю между лиспом и хаскелем, склоняюсь в пользу последнего, хотя на первом у нас на работе есть проект, с которым я даже периодически косвенно сталкиваюсь. Но второй вроде как моднее/современнее, да и в вакансиях иногда мелькает.

Так вот, что лучше взять для изучения Хасекля? Курта или Липовача? Первая вроде посовременнее, но и цена +500р. Стоит ли оно того?

Все пишут книги по Haskell

Fri, 04 Jan 2019 08:55:16 GMT

Некоторое время назад вышел перевод книги Программируй на Haskell.
Книга для начинающих.
Решил поискать есть ли что-нибудь для тех кто уже что-то знает.
Нашел следующее (большая часть книг еще пишется):
Haskell in Depth
Thinking with Types
Intermediate Haskell
The Joy of Haskell
Haskell programming from first principles
Haskell Almanac

Такое впечатление, что что-то происходит. Haskell стали использовать в production?
P.S. Ревью некоторых книг от одного из авторов.

Cloverage и maven- как?

Wed, 02 Jan 2019 09:05:22 GMT

Есть ли у кого success story, как запустить cloverage хотя бы и из командной строки, а лучше из maven-execute-plugin, не связываясь с leiningen?

Жизнь с Clojure в окружении Java

Wed, 19 Dec 2018 20:31:39 GMT

Прицепил Clojure в связку модулей, код вызывается и отдаёт (пока ещё ничего не отдаёт) в Java. Ну learning curve у него довольно steep. Нагенерить жавских интерфейсов и классов заняло полтора дня с гуглением. Понимаю, что тупой. Поддержите что-ли, что дальше должно быть легче. Осталось перенести простую логику чтения JSON с Groovy в этот новый код на Clojure.