Vladislav
Дерево это частный случай графа, для него легко изоморфизм считать
Vladislav
Просто от корня идти
Anonymous
Дерево это частный случай графа, для него легко изоморфизм считать
я уже не помню что там по O(n), но всякое легче, чем на граф без доп.огранчиений.
Anonymous
но не суть, пусть автор на досуге подумает или это действительно задача нахождения изоморфизма или нет.
Anonymous
но я че-то думаю, что это нифига нелегко. а экспоненциальный взрыв.
Anonymous
речь о всех способах, которыми дерево вывражений в "нормальной форме" (а она вообще существует, ксттати?) можно переписать в ненормальную? это бесконечно большое множество, вопрос в том, счетное ли или нет
Anonymous
скорее всего, даже несчетное
Anonymous
f () = true, f () = !! true, f () = !! !! true
Anonymous
несчетное
Ilya
Вроде такая же функция) Возьму ее лучше
Alexander
Какой-то проры чатика формальной верификации
Alexander
там похожим занимаются
Anonymous
Ilya
А где он? Поделишься ссылкой?
Наверное, речь про это https://t.me/joinchat/Bf3AJw969zOLpLQEVAmMjQ
Ilya
У меня есть такая штука: readFile :: FilePath -> IO String mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b) sourceCodeFilePaths :: [FilePath] (mapM readFile sourceCodeFilePaths) :: IO [String] А я бы хотел такую: [(FilePath, IO String)] или даже Maybe [(FilePath, String)] Возможно ли так сделать? Я пробую так, но что-то не сходится: map (\fp -> (fp, readFile fp)) sourceCodeFilePaths
Anonymous
А почему не [Maybe (FilePath, String)]?
Ilya
А почему не [Maybe (FilePath, String)]?
Возможно, так даже лучше. Но пока непонятно, как это сделать
Anonymous
Возможно, так даже лучше. Но пока непонятно, как это сделать
Ну внутри IO пытаться читать файл и в случае успеха - just, в случае отсутствия файла такого или другой беды - nothing. Точных названий функций на память не помню, но есть hoogle.
Ilya
>внутри IO пытаться читать файл А вот это что означает? Я могу вызвать readFile и получить IO String, но непонятно, как оттуда попытаться достать String. Нашел некий liftIO, но, судя по исходникам, это id https://hackage.haskell.org/package/base-4.12.0.0/docs/src/Control.Monad.IO.Class.html#liftIO
Denis
чтобы применить функцию на String из IO String, нужно использовать fmap/bind
Denis
fmap: transform <$> getString >>=: do s <- getString let s’ = transform s …
Denis
это самая база, чтобы хоть как-то на хаскелле писать - это нужно знать
Ilya
mapM (\fp -> (fp,) <$> readFile fp) fps
Отлично, так работает (но без TupleSections я сделал (,) fp Пойду почитаю про <$> теперь. Судя по типам, это fmap, так?
Ilya
Внутри IO ты получишь именно String. Примеры там выше скинули.
Это-то ясно. Не ясно, как сделать IO a -> Maybe a
Anonymous
Это-то ясно. Не ясно, как сделать IO a -> Maybe a
Никак. Из IO нельзя выйти. Но внутри IO можно пользоваться чистыми функциями
Denis
никак
Ilya
А почему не [Maybe (FilePath, String)]?
А как тогда сделать так?
Ilya
Внутри IO
Anonymous
IO это твоя Вселенная, из нее не выйдешь
саша
Это-то ясно. Не ясно, как сделать IO a -> Maybe a
(``catch`` const (pure Nothing)) . fmap Just :: IO a -> IO (Maybe a) Двойные бэкквоты заменить на одинарные
Alexander
Но не надо так делать, если не понимаешь, что это такое и какие побочные эффекты словишь
Alexander
Выше все верно сказали, что можно остальные вычисления поднять в IO
Anonymous
Не путайте парня, что ж вы за изверги такие
Anonymous
Он же простых вещей с IO пока не понимает.
Anonymous
Суть в том, что внутри IO a, где a есть произвольный тип, ты работаешь конкретно с a. И потому все твои чистые функции вполне применимы. Но избавиться от IO нельзя. Входишь в IO > используешь свои чистые функции как надо > выходишь в IO.
Anonymous
Это позволяет тебе отделить чистую составляющую кодовой базы от грязной.
Ilya
Суть в том, что внутри IO a, где a есть произвольный тип, ты работаешь конкретно с a. И потому все твои чистые функции вполне применимы. Но избавиться от IO нельзя. Входишь в IO > используешь свои чистые функции как надо > выходишь в IO.
В этом описании выходит так, что я вхожу в IO, когда начинаю выполнять программу (условно), а выхожу, когда программа завершается. Но внутри программы-то я могу снова вызвать функцию и получить в качестве ее результата IO b
Ilya
Это (\fp -> (,) fp <$> readFile fp) можно как-то короче записать? Например, опустив fp
Anonymous
И никуда от IO тебе не деться
Ilya
Да, внутри IO может быть ещё IO, но это всё тот же IO
Что здесь означает "тот же"?
Anonymous
саша
Это (\fp -> (,) fp <$> readFile fp) можно как-то короче записать? Например, опустив fp
sequence . liftA2 (,) id readFile Как-то так, но не похоже, что это короче
Anonymous
Но там разумеется все глубже гораздо. Сейчас запутают тебя.
Anonymous
Для начала достаточно думать, что от IO нельзя избавиться и внутри него можно пользоваться чистыми функциями. И нужно.
Alexander
У нас есть контексты, IO, Maybe, Either a и т.п.
Alexander
Для того, чтобы связывать действия в этих контекстах нужно или поднимать чистую функцию (fmap)
Alexander
Т.о. чистая функция оказывается функцией в контексте
Alexander
Или использовать bind, apply если у тебя функция с эффектом
Alexander
Для того, чтобы "снять"/выполнить эффект, тебе нужен доступ к конструктору
Alexander
например ты можешь пропаттерн-матчить Maybe, или вызвать функцию maybe
Alexander
Конструктору типа данных, который реализует твой эффект
Alexander
Отличие IO заключается в том, что тебе не доступен его конструктор
Anonymous
Это ясно, спасибо
Вообще, насколько я знаю, абсолютно любая программа хаскеля выполняется внутри IO, хотя твой main может даже не иметь такого типа.
Alexander
и ты не можешь написать case foo of (IO# x)
Alexander
Поэтому ты не можешь "снять" эффект IO
Alexander
а единственная снималка эффекта доступная вне unsafe функций это main
Alexander
Если бы у тебя констркуторы Just и Nothing и функция maybe не были бы экспортированы, то Maybe была бы такой же "магической" вещью
Anonymous
В этом описании выходит так, что я вхожу в IO, когда начинаю выполнять программу (условно), а выхожу, когда программа завершается. Но внутри программы-то я могу снова вызвать функцию и получить в качестве ее результата IO b
Фишка в том, что вот существует такая хитроумная функция IO > IO > IO, она-то и позволяет этому быть. И есть она не только на IO, а является частью очень важного механизма в ФП вообще и в частности - в Хаскеле.
Alexander
> Это (\fp -> (,) fp <$> readFile fp) можно как-то короче записать? Например, опустив fp есть програмка pointfree и сайт pointfree.io
Alexander
можно там ввести то, что ты хочешь превратить в pointfree форму и оценить хочешь ли ты читать такой код
Alexander
Например для этой функции он предлагает: liftM2 (<$>) (,) readFile
Alexander
я бы, правда, не хотел читать такой код и угадывать, что тут используются (->) и IO
Alexander
Но по-началу я бы советоввал всем пытаться прогонять свой код через pointfree, хотя бы для того, чтобы выработался вкус и чувство, где стоит сокращать, а где нет
Dmitry
Мне кажется, так достаточно понятно: (,) <$> pure <*> readFile
Alexander
понятно, но даже типы не сходятся.. (,) <$> pure <*> readFile :: Applicative f => FilePath -> (f FilePath, IO String) :t (\fn -> (fn,) <$> readFile fn) (\fn -> (fn,) <$> readFile fn) :: [Char] -> IO ([Char], String) :t liftA2 (<$>) (,) readFile liftA2 (<$>) (,) readFile :: FilePath -> IO (FilePath, String)
kosc
Чем в этом вашем хаскеле можно сконвертить 1251 в utf8? А то в последнем lts нет пакета encoding. Что-то более актуальное появилось или что?