Ответы пользователя по тегу Функциональное программирование
  • Копируется ли состояние при каждой операции над монадой состояния в Haskell?

    Копируется, только надо учитывать ленивость и чистоту Хаскеля.
    Если взять обычный список и класть ему в голову - ничего не надо будет копировать, так как добавление головы не требует копирования хвоста, новый список будет просто ссылаться на хвост. Удаление головы (т.е. взятие хвоста) тоже не требует создавать копий.
    Если же вы будете в качестве состояния использовать какой-либо строгий тип данных, да с unboxed членами, тот да, будет копироваться.
    Надо учитывать так же и другую вещь: накопление thunk'ов. Например, если состояние - это число, и вы миллион раз сделаете modify (+1), по факту там будет лежать отложенное вычисление на миллион прибавлений единиц, что будет кушать память. Потому есть строгая монада state, а также modify', который форсирует применение переданной функции.
    Ответ написан
  • Какой ФП язык выучить?

    Если в академических, то, как ответили выше, учите Haskell, а лучше [сразу или потом] Agda2 с зависимыми типами, узнаете много нового.
    Ответ написан
  • Что такое список в функциональных языках программирования?

    Отвечу за Haskell.
    Вот список:
    data [a] = [] | a : [a]
    Т.е. список либо пуст, либо имеет [ссылку на] [недовычисленную] голову и [ссылку на] [недовычисленный] другой список - хвост. Т.о. чтобы пробежаться по списку (без использования готовых функций), надо проверять, не является ли он пустым, если нет, работать с головой, а хвост обрабатывать рекурсивно.
    Список иммутабельный, т.е. ничего никуда вставить нельзя, однако списки могут "шарить" общий хвост, например:
    list1 = [2,3,4]
    list2 = 1 : 2 : list1
    list3 = 0 : 0 : list1

    В памяти будет (после форсирования, рассмотрение ленивости я опускаю) как-то так:
    1-2
       \
        2-3-4
       /
    0-0
    Ответ написан
  • Как рекурсивно распарсить скобки?

    Во-первых, заменим splitOn " " на words, который съест все пробелы. Далее, concat $ map ... - это то же, что и concatMap .... Рассмотрим sepBr. Он берёт строку без пробелов и делит её на куски, если там есть операторы, числа или скобки. Если строка уже пустая, результат - пустой список. Если строка непустая, то возможны варианты. Если первый её символ - какая-то скобка, отделяем эту скобку, а остальное делим опять при помощи sepBr. Иначе делаем так: разделим строку, чтобы сначала шли только цифры: span isDigit и посмотрим, что получилось. Если цифры есть - отделяем их, а остальное опять делим sepBr. Если цифр нет, то просто отделяем первый символ. Вот, что получилось:
    sep ∷ String → [String]
    sep = concatMap sepBr . words where
    	sepBr ∷ String → [String]
    	sepBr "" = [] -- нечего делить
    	sepBr s'@(x:xs)
    		| x `elem` "()" = [x] : sepBr xs -- скобка
    		| otherwise = case span isDigit s' of -- возьмём цифры
    			("", t:tl) → [t] : sepBr tl -- нет цифр, берём первый символ остатка
    			(n, tl) → n : sepBr tl -- есть цифры, их отдельно


    По поводу вашего второго варианта.
    if word == [] then [] else head word - т.е. a либо пустой список, либо символ, типы не совпадают. Но в вашем случае word не может быть пустым, ведь выше уже был паттерн sepBr "", так что можно просто оставить a = head word
    Далее, что такое ab? Это [a] ++ b, т.е. [head word] ++ init (tail word), т.е. это то же, что и просто init word. Аналогично bc = tail word. Вместо того, чтобы брать отдельно head и отдельно tail, можно воспользоваться паттерн-матчингом и записать (a : bc) = word.
    С учётом этого ваш вариант переписывается в
    sep2 ∷ String → [String]
    sep2 = concatMap sepBr . words where
    	sepBr ∷ String → [String]
    	sepBr ""  = []
    	sepBr " " = []
    	sepBr word
    		| a `elem` brackets = [[a]] ++ sepBr bc
    		| c `elem` brackets = sepBr ab ++ [[c]]
    		| otherwise = ([a : bc])
    		where
    			(a : bc) = word
    			c = last word
    			ab = init word
    			brackets = ['(', ')']

    И он вполне работает.
    Ответ написан
  • Поясните про замыкания в ФП?

    Чистая. Рассмотрим foo = add 2, foo x для некоторого x всегда возвращает одно и то же значение, а также не производит никакого эффекта, наблюдаемого извне, и потому подпадает под определение чистой функции. Т.е. foo = add 2 идентичен функции foo x = 2 + x, которая, очевидно, чистая.
    Ответ написан