lomeo: (лямбда)
Я это как-то писал, но напишу ещё раз, бо тема поднялась.

Недостатки явной рекурсии по сравнению с комбинаторами (ага, zip3):

  • Рекурсия непонятна (согласен, это субъективное).
  • Обычно используется с декомпозицией, нарушая инкапусляцию.
  • Всегда используется для работы с элементами, вместо работы с коллекцией (wholemeal programming).
  • Цепочка вызовов проще для оптимизации.
  • Сложнее нежно мною любимый equational reasoning.

Юный хаскеллист, избегай явной рекурсии!

Ну и ссылочка, куда без неё!
lomeo: (лямбда)
Клёвая реализация сабжа от [livejournal.com profile] antilamer:
data Tree a = Nil | Branch (Tree a) a (Tree a)

bfs t = [x | Branch _ x _ <- b]
  where
    b = t:[x | Branch l _ r <- b, x <- [l,r]]

Ленивость, все дела.

отсюда.
lomeo: (лямбда)
Скажите, пожалуйста, кто что использует для arbitrary precision computations в Haskell? Интересует аналог BigDecimal в java - при делении задаём режим округления, можно использовать для денег. Ну и важно иметь человеческий Read/Show.

Кроме библиотеки Jeremy Shaw есть что-нибудь стоящее? Мне не нравится, что она не на hackage и у неё есть (небольшие) проблемы с делением.
lomeo: (лямбда)
Две библиотеки, о которых узнал из френд-ленты. Понравились.

1. mmtl via [livejournal.com profile] permea_kra.

Очередная библиотека монад-трансформеров с фишкой. Позволяет не определять для каждой монады инстанс каждого монад-класса. Таким образом модуль с ReaderT не будет ничего знать о MonadWriter, тем не менее инстансы для

(а) MonadWriter w => MonadWriter w (ReaderT r (Writer w))
и
(б) MonadWriter w m => MonadWriter w (ReaderT r (WriterT w m))

будут выводиться. Т.е. теперь мы пишем свой монад-трансформер и у нас автоматом есть инстансы для всех имеющихся монад классов.

К сожалению, (а) и (б) реализованы как отдельные инстансы. Была бы ещё возможность описать это в отдельном - типа
MonadWriter w i, MonadTrans t => MonadWriter w (t i)


Написано, что "Inspired by the paper /Functional Programming with Overloading and Higher-Order Polymorphism/, Mark P Jones"

2. Coroutine via [livejournal.com profile] nponeccop.

lightweight session types для описания протоколов. Индексированная монада для представления линейных типов, собирание типов с помощью комбинаторов типов. Понравилась реализация дуальности типа клиента и сервера - очень просто и красиво.

Подробнее в презентации Haskell Session Types with (Almost) No Class
от Jesse Tov. Есть видео, но я его не смотрел.
lomeo: (лямбда)
Аналог uniplate, не зацикливающийся на рекурсивных данных. На основе кода [livejournal.com profile] permea_kra (спасибо!).

Код на hpaste (отсюда)

Пример использования
data Rose = Rose { roseId :: Int, roses :: [Rose] }
    deriving (Data,Typeable)

testRose = let
        a = Rose 1 [b,c]
        b = Rose 2 [a,c]
        c = Rose 3 [a,b]
    in a

Работаем...
> [id | Rose id _ <- recUniplate testRose]
[1,2,3]

Ключевые слова: SYB, StableName, unsafePerformIO
lomeo: (лямбда)
На RSDN Tonal- задаёт вопрос о сериализации взаимно-рекурсивных данных.

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

Поэтому в голову приходит замечательный пакет data-reify от Andy Gill. О его применении можно прочитать в статье Type-Safe Observable Sharing in Haskell.

Смысл в том, что мы можем разложить рекурсивные данные на нерекурсивные данные со ссылками - то, что нам и нужно.
Read more... )
Покритикуйте.
lomeo: (лямбда)
[livejournal.com profile] nealar сейчас в haskell@c.j.r показал на partial signatures от Олега.

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

Второй случай рулит.

fixIO

Apr. 6th, 2009 07:13 pm
lomeo: (лямбда)
Предыстория: http://thesz.livejournal.com/950788.html?thread=7471620#t7471620

Т.е. предполагалось, что любой mdo можно развернуть в letrec (т.е. do без mfix).
Read more... )
lomeo: (лямбда)
Понадобилось мне состояние, вычисление которого можно прервать в любой момент. Комбинатор guard не подходит тем, что его просто нет для State. if/then/else не устравает, потому что иногда прерывать необходимо в любом месте, например, в одной из вызываемой функции рекурсивной функции:
loop = do
    modify (+1)
    check
    loop

check = do
    s <- get
    if s == 42
        then interrupt
        else return ()

Вот как тут описать комбинатор interrupt?
Read more... )

downcasting

Feb. 5th, 2009 12:15 pm
lomeo: (лямбда)
Downcasting - операция, как известо, опасная. К сожалению, совсем избавиться от неё нельзя1. Например, в случае, если мы работаем с колбэками, принимающими параметры, типы которых надо понизить в самих колбэках. Или вспомним обычный метод equals в Java.

Но, раз нельзя избавиться, то мы можем по крайней мере постараться снизить его опасность. Read more... )
lomeo: (лямбда)
На RSDN я очередной раз дискутировал с VladD2 и, кстати, для меня дискуссия получилась довольно полезной. Речь шла, в частности, и о Haskell. Один из необсуждённых (пока?) тезисов высказал VladD2:

Лично по мне так чем дальше инструмент от математического смысла, тем лучше.

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

Read more... )
lomeo: (лямбда)
К чему я так подробно расписывал получение свёртки для розы? Очевидно, что интуитивно получить её можно сразу. Так я обычно и делаю, воспользовавшись методом размерностей, пардон, программированием "от типов". Возможно, так делаете и вы. Я хочу показать главный недостаток этого подхода - он неформален.

Read more... )

В данном конкретном случае нам очень сильно помогает Curry-Howard, но он не гарантирует уникальности доказательства (реализации), т.е. этот метод не формализуем. А вот на основе ТК, думаю, можно построить CataEval.
lomeo: (лямбда)
3-й parsec, как известно, построен для работы с Data.ByteString, что должно неимоверно поднять скорость парсинга, по сравнению с обычным строковым.

Посмотрим, так ли это на самом деле )
lomeo: (лямбда)
Расширения типа fundep или MPTC обычно понятны бывают сразу, ну, по крайней мере, их идея. А вот чтобы разобраться с ошибками при инстанциировании класса, придётся разобраться.

Read more... )
lomeo: (лямбда)
Я вот жаловался [livejournal.com profile] thesz, что в Haskell нет аналога partial function в Scala, чтобы можно было легко строить конструкции аналогично Erlang'овского receive (я говорю о синтаксисе). Однако механизмы есть. Правда, я нашёл пока только для IO.

import Prelude hiding (catch)
import Control.Exception

e `patternFail` h = e `catch` \(PatternMatchFail _) -> h

apply handlers = \x -> foldl1 patternFail (map ($x) handlers)

-- *Main> apply [\[1]->putStrLn "a", \[2]->putStrLn "b", \[3]->putStrLn "c"] [2]
-- b


Список здесь всего лишь пример, можно сделать и по другому (varargs?)
lomeo: (лямбда)
Только недавно понял, что это то же самое, что и GADT:

data Z
data S n

data family List n a
data instance List Z a = Nil
data instance List (S n) a = Cons a (List n a)

--например
cadr :: List (S (S n)) a -> a
cadr (Cons _ (Cons x _)) = x


Только их ещё и расширять можно. Так что алгебраические типы данных, которые можно выписывать в разных модулях уже есть :-)
lomeo: (лямбда)
Заинтересовал меня всё таки [livejournal.com profile] kurilka тотальным ФП, а у [livejournal.com profile] deni_ok и [livejournal.com profile] thesz я понахватался ссылок и умных слов. Ну, ещё и dependent types в стороне не остались.

Подумал, что total fp будет неплохо смотреться для программирования на типах - гарантия завершения будет тут очень кстати.

К сожалению, "по семейным обстоятельствам" я сейчас не в силах заняться чем нибудь серьёзно, поэтому всё, что я здесь пишу - скорее для себя, чтобы не забыть. Написано очень нудно (это тоже для себя, извините - я тупой) и сумбурно (а это так получилось).

Итак что здесь? (чтобы вы решили читать или нет)
Здесь размышления о том, как должен работать тайпчекер в системе с зависимыми типами. Я пытаюсь придумать приёмы, позволяющие строить гарантировано завершающиеся доказательства/опровержения.

Итак, о чём думал, пока ужинал макаронами. )

Если у кого то есть материалы по теме, накидайте сюда плз - потом как руки дойдут обязательно прочту всё-всё-всё :-)
lomeo: (лямбда)
Небольшое вступление.

Есть такой модуль Control.Applicative, в котором определён класс Applicative

class Functor a => Applicative a where
    pure :: a -> f a
    <*> :: f (a -> b) -> f a -> f b


т.е. он чуть шире Functor (за счёт pure), и чуть уже Monad. Золотая середина - полезно, когда нам от монад нужен только return.

тут мне непонятно )

Profile

lomeo: (Default)
Dmitry Antonyuk

December 2015

S M T W T F S
  12345
6789101112
131415 16171819
20212223242526
2728293031  

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 22nd, 2017 04:45 pm
Powered by Dreamwidth Studios