deniok: (Default)
2017-01-24 08:22 pm

Инхабитаты зашкаливающих порядков

Инхабитация fmap для монад Cont и Sel - мой любимый дополнительный вопрос на экзамене. Справитесь?
? :: (a -> b) -> ((a -> r) -> r) -> ((b -> r) -> r)
? :: (a -> b) -> ((a -> r) -> a) -> ((b -> r) -> b)
Чтобы помучить студентов посильнее я предлагаю проинхабитировать (<*>) для Cont:
? :: (((a -> b) -> r) -> r) -> ((a -> r) -> r) -> ((b -> r) -> r)
А вот (<*>) для Sel я студентам на экзаменах не даю. Может стоило бы?
? :: (((a -> b) -> r) -> (a -> b)) -> ((a -> r) -> a) -> ((b -> r) -> b)
(Те, кто вызывает джинна, заведомо считаются проигравшими.)
deniok: (ухмыляюсь)
2016-11-18 09:37 pm

Ратный труд обертки-композитора

Как известно композиция двух функторов является функтором, причем fmap для этой композиции - это композиция fmap'ов:
GHCi> (fmap . fmap) (^2) [Just 3,Just 5,Nothing]
[Just 9,Just 25,Nothing]
Левый fmap протаскивает свой аргумент (fmap (^2)) через конструкторы списка, а дальше оставшийся fmap протаскивает свой аргумент (^2) через конструкторы Maybe.

а фолды? траверсы? аппликативы? монады?... )
deniok: (ухмыляюсь)
2016-11-06 10:47 pm

Minimal Incomplete Definition

data Id a = Id {runId :: a} deriving (Eq,Show)

instance Traversable Id where
  sequenceA (Id x) = pure Id <*> x
 
instance Functor Id where
  fmap = fmapDefault

instance Foldable Id where
  foldMap = foldMapDefault
Какие неожиданные эффекты будут сопровождать следующий вызов, и в чем их причина?
GHCi> traverse Just (Id 5)

deniok: (ухмыляюсь)
2016-11-06 12:55 pm

Не допускайте потери неоднозначности

Часто парсеры пишут в виде, допускающем разбор неоднозначных грамматик
newtype Parser a = Parser { apply :: String -> [(a, String)] }
(Тип apply это не что иное, как стандартный ReadS.) Однако, начав таким образом, лучше быть консистентным, поддерживая эту возможность повсюду, например
parse :: Parser a -> String -> [a]
parse p = map fst . filter (null . snd) . apply p
Сделайте приведенный выше парсер представителем Applicative и Alternative, так чтобы обеспечить следующее поведение
> twoChars x = (\a b -> [a,b]) <$> char x <*> char x
> threeChars x = (\a b c -> [a,b,c]) <$> char x <*> char x <*> char x
> parse (some (twoChars '7') <|> some (threeChars '7')) "777777"
[["77","77","77"],["777","777"]]
(Парсер char, конечно, еще потребуется, но тут, надеюсь, все справятся.)
deniok: (ухмыляюсь)
2016-07-27 02:01 pm

Свернуть сворачиваемое в альтернативу

В стандартной библиотеке (Data.Foldable) имеется функция
> :t asum
asum :: (Alternative f, Foldable t) => t (f a) -> f a
> asum [Nothing, Just 1, Just 2]
Just 1
> asum [[1,2,3],[4,5]]
[1,2,3,4,5]
Можете ли вы написать afold с естественной для своего типа семантикой:
> :t afold
afold :: (Alternative f, Foldable t) => t a -> f a
>  afold "abc" :: Maybe Char
Just 'a'
>  afold "abc" :: [Char]
"abc"
Я знаю три решения: кривое (требующее FlexibleInstances и IncoherentInstances), обычное (утилизирующее избыточно богатый интерфейс Foldable) и современное, элегантно выпрямляющее кривизну кривого.
deniok: (ухмыляюсь)
2016-07-23 11:23 am
Entry tags:

Собрал все в одном месте...

... и педантично выровнял:
($)    ::                      (a -> b) ->   a ->   b
(<$>)  :: Functor     f  =>    (a -> b) -> f a -> f b
(<*>)  :: Applicative f  =>  f (a -> b) -> f a -> f b
(=<<)  :: Monad       m  =>  (a -> m b) -> m a -> m b

(&)    ::                      a ->   (a -> b) ->   b  -- Data.Function
(<&>)  :: Functor     f  =>  f a ->   (a -> b) -> f b  -- Control.Lens.Operators
(<**>) :: Applicative f  =>  f a -> f (a -> b) -> f b  -- Control.Applicative
(>>=)  :: Monad       m  =>  m a -> (a -> m b) -> m b
deniok: (ухмыляюсь)
2016-06-18 12:17 am
Entry tags:

Кишки наружу

Все-таки оставили:
GHCi> :i ($)
($) ::
  forall (r :: GHC.Types.RuntimeRep) a (b :: TYPE r).
  (a -> b) -> a -> b
        -- Defined in `GHC.Base'
infixr 0 $
GHCi> :i undefined
undefined ::
  forall (r :: GHC.Types.RuntimeRep) (a :: TYPE r).
  GHC.Stack.Types.HasCallStack =>
  a
        -- Defined in `GHC.Err'
Хорошо хоть
> :t ($)
($) :: (a -> b) -> a -> b
> :t undefined
undefined :: a
deniok: (ухмыляюсь)
2016-06-12 07:01 pm

Инфиксный аналог fmap

В выражении
GHCi> succ <$> "abc"
"bcd"
оператор <$> имеет тип (Char -> Char) -> [Char] -> [Char]. Верно ли это утверждение для обоих вхождений <$> в следующем выражении
GHCi> succ <$> succ <$> "abc"
"cde"
deniok: (ухмыляюсь)
2016-04-07 12:00 pm

id да не id

Приведите пример таких объявлений типа данных с конструктором данных T и сигнатуры функции f, что реализация
f (T x) = T x
проходила бы проверку типов, a
f x = x
нет.
deniok: (ухмыляюсь)
2016-03-07 05:09 pm
Entry tags:

Текущее состояние длин

Померил тут, похоже про магические хэши не надо рассказывать. Тут length' - текущая реализация из GHC, length0 - трех?летней давности:
{-# LANGUAGE MagicHash #-}
module Length where

import GHC.Prim
import GHC.Exts (Int(I#))
import Data.List

length0    :: [a] -> Int
length0 l  =  len l 0#
  where
    len           :: [a] -> Int# -> Int
    len []     a# =  I# a#
    len (_:xs) a# =  len xs (a# +# 1#)

length' :: [a] -> Int
length' xs = lenAcc xs 0 where
  lenAcc []     n = n
  lenAcc (_:ys) n = lenAcc ys (n+1)

length'' :: [a] -> Int
length'' = foldl' (const . succ) 0

length''' :: [a] -> Int
length''' []     = 0
length''' (_:xs) = 1 + length''' xs
Результаты
C:\Users\deniok\Documents\Haskell>ghc -O2 Length.hs
[1 of 1] Compiling Length           ( Length.hs, Length.o )

C:\Users\deniok\Documents\Haskell>ghci Length.hs
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Ok, modules loaded: Length.
> :set +s
> length [1..100000000]
100000000
(1.56 secs, 8,014,793,624 bytes)
> length0 [1..100000000]
100000000
(1.55 secs, 8,002,029,776 bytes)
> length' [1..100000000]
100000000
(1.55 secs, 8,001,085,992 bytes)
> length'' [1..100000000]
100000000
(2.00 secs, 9,601,216,960 bytes)
> length''' [1..100000000]
*** Exception: stack overflow
>
> length [1..50000000]
50000000
(0.86 secs, 3,938,034,240 bytes)
> length0 [1..50000000]
50000000
(0.84 secs, 3,937,631,120 bytes)
> length' [1..50000000]
50000000
(0.84 secs, 4,240,225,000 bytes)
> length'' [1..50000000]
50000000
(1.08 secs, 4,845,463,912 bytes)
> length''' [1..50000000]
50000000
(1.34 secs, 4,420,898,928 bytes)
deniok: (Рыжий)
2016-02-18 05:16 pm
Entry tags:

Рекурсивная взаимность

Между Haskell Report и GHC base имеется дивная взаимная рекурсия.

В GHC base мы имеем такое определение наименьшей неподвижной точки (least fixpoint)
fix :: (a -> a) -> a
fix f = let x = f x in x

В Haskell Report в разделе 3.12 описана трансляция для выражения let в ядро (привожу только релевантные правила)
...
let p = e1 in e0    =    case e1 of ˜p -> e0
                             where no variable in p appears free in e1
let p = e1 in e0    =    let p = fix (\˜p -> e1) in e0
с замечанием "where fix is the least fixpoint operator".

Чтобы понять рекурсию, нужно понять рекурсию.
deniok: (ухмыляюсь)
2016-01-27 07:20 pm
Entry tags:

Присваивание

А вот скажите, пожалуйста, та идея что присваивание полю структуры может менять не только значение, но и тип структуры, она помимо кметтовских линз где-нибудь еще в статически типизированных языках реализована?
> ('z', True) & _1 .~ 42
(42, True)


UPD. Мне тут делают совершенно резонное замечание, что стандартный синтаксис модификации записей в Хаскеле обладает этим свойством:
> data Pair a b = Pair {fstP :: a, sndP :: b} deriving Show
> let p1 = Pair True 'z'
> :t p1
p1 :: Pair Bool Char
> let p2 = p1 {fstP = 42}
> :t p2
p2 :: Num a => Pair a Char
У меня это совершенно вылетело из головы.
deniok: (Рыжий)
2015-11-05 10:33 pm

Экспоненциальное офункторивание

Как вам скорее всего известно, написать представителя класса типов Functor для типа эндоморфизма невозможно. Если неизвестно, то можете попробовать
newtype Endo a = Endo (a -> a)

instance Functor Endo where
   fmap f (Endo g) = Endo undefined
Даже если ваш результат сойдется по типам, законам для функтора он удовлетворять не будет.

Вот вам другой экспоненциальный тип данных, для которого, однако, написать законного представителя класса типов Functor можно:
newtype Quest b a = Quest ((a -> b) -> a)

instance Functor (Quest b) where
  fmap f (Quest g) = Quest undefined
Попробуйте сделать это, после чего ответьте на вопрос: чему равен результат такого вызова
> let Quest f = fmap succ $ Quest (\h -> h 40) in f id
deniok: (пацифик)
2015-10-24 11:51 am

плюс траверсабилизация всех фолдаблов

Объясните, почему невозможно по представителю Foldable для конструктора типа сгенерировать представителя Traversable.
deniok: (typed lambda)
2015-10-01 12:29 am

Про seq

Как известно seq вычисляет свой первый аргумент до слабой заголовочной нормальной формы (WHNF). Не пользуясь GHCi, ответьте на вопрос, каково будет значение следующего выражения
Prelude> (\True y -> ()) False `seq` 5
Проверьте себя в GHCi. Какова будет полученная в первом аргументе seq WHNF?

UPD. А теперь вопрос на засыпку: каково будет значение следующего выражения
Prelude> (\True -> \y -> ()) False `seq` 5
Считаете ли вы это правильным?
deniok: (пацифик)
2015-09-30 12:07 pm
Entry tags:

Вопрос про WHNF

А вот подскажите, на Haskell Wiki вот тут в последнем абзаце дурь написана, да? Никакой разницы между встроенными и пользовательскими частично примененными функциями нет?
Prelude> (+) undefined `seq` 5
5
Prelude> const undefined `seq` 5
5
Prelude> (\x y -> x) undefined `seq` 5
5
Или это только в последней версии GHC?

UPD. Нет, понял, там все верно, сам дурак. Пусть висит, демонстрирует мою глупость urbi et orbi.
deniok: (Рыжий)
2015-09-11 01:39 pm

Онлайн-курс по Хаскелю

Через неделю запускаем на stepic.org вводный онлайн-курс по Хаскелю Функциональное программирование на языке Haskell.

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

В день, когда я закончил записываться, вышла новая версия Haskell Platform. C реализованными Functor-Applicative-Monad proposal и Foldable/Traversable in Prelude proposal. Очень своевременно. Типы кучи функций над списками в Prelude поменялись на более общие, Applicative я вообще не рассказывал, иначе в формат не уложиться было. Включил рекомендацию ставить прошлую версию Haskell Platform, либо пользоваться последней на свой страх и риск.

Организационно в CS Center все как всегда замечательно. Отдельное спасибо Кристине и Леше! Во всех вузах надо разогнать весь административно-бюрократический аппарат к чертям собачьим, на учебном и научно-исследовательском процессах это скажется немедленно и самым благотворным образом.

deniok: (Рыжий)
2015-03-30 12:08 pm
Entry tags:

Traversable is Foldable, а мы-то тут при чем?

Размышляю тут вторые сутки над вопросом, что делает контекст Foldable в определении класса типов Traversable
class (Functor t, Foldable t) => Traversable t where
  ...
Технически он не нужен: никакая функциональность Foldable не используется ни при выражении законов Traversable, ни для реализации по умолчанию его методов.

Контекст Functor, кстати, не вызывает вопросов в техническом отношении: он нужен и для формулировки законов (Naturality и Composition для sequenceA и Composition для traverse) и для реализации по умолчанию
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

Соображения, которыми руководствовались разработчики класса типов Traversable, включая контекст Foldable, заключаются в довольно разумном соображении: любой Traversable является Foldable в том смысле, что имея traverse можно гарантированно и универсально реализовать Foldable с помощью нехитрой машинерии:
foldMap :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = getConst . traverse (Const . f)
(эта функция присутствует в Data.Traversable под именем foldMapDefault).

Тем не менее решение о "наследовании" Traversable от Foldable имеет свою цену. Теперь, объявляя некоторый тип MyType представителем Traversable, я должен сначала сделать его представителем Foldable. Даже если я совсем не собираюсь пользоваться Foldable-интерфейсом, я должен написать затычку
instance Foldable MyType where
    foldMap = foldMapDefault
Это не очень большая цена, но представим, что через пару лет ресерчеры обнаружат, что есть замечательный класс типов SomethingInterestingAndTrendyable и что с помощью traverse можно реализовать его единственную ключевую функцию somethingInterestingAndTrendyImpl. То есть Traversable является (is a :)
SomethingInterestingAndTrendyable и поэтому нужно сделать
class (Functor t, Foldable t, SomethingInterestingAndTrendyable t) => Traversable t where
  ...
а для "удобства" добавить somethingInterestingAndTrendyImplDefault. Не думаю, что мы будем этим очень довольны, хотя технически в каждый наш инстанс Traversable потребуется добавить лишь
instance SomethingInterestingAndTrendyable MyType where
    somethingInterestingAndTrendyImpl = somethingInterestingAndTrendyImplDefault


Но раз уж мы двинулись по этому пути "проявленных наследований" (а мы таки двинулись, см. Monad и Applicative), почему бы не переложить эту деятельность на компилятор? Вроде есть напрашивающееся решение: разрешить в Хаскелле в классах-наследниках задавать методы по умолчанию для классов-родителей. То есть вместо внешней по отношению к классу foldMapDefault и ей подобных разрешить писать
class (Functor t, Foldable t, SomethingInterestingAndTrendyable t) => Traversable t where
    -- default impls for Traversable methods
    traverse = ...
    -- default impls for parents methods
    fmap f = getId . traverse (Id . f)
    foldMap f = getConst . traverse (Const . f)
    somethingInterestingAndTrendyImpl = ...
В этом случае словари для родительских классов могут при необходимости генерироваться автоматически (если у нас достаточно реализаций по умолчанию), и разработчики будут освобождены от написания фейковых родительских инстансов.

Discuss.

UPD. В комментах сказали, что proposal такой имеется. Нашел, https://wiki.haskell.org/Class_system_extension_proposal, почитал. Мрак. C++ как мы его знаем, практически все прелести разрешения коллизий при множественном наследовании реализации. Нам такого не надо. Вывод: наследование - зло, его надо избегать, долой контекст Foldable из Traversable (и, как мне тут подсказывают, Applicative из Monad).
deniok: (Рыжий)
2015-03-27 12:08 pm
Entry tags:

Свершилось!

GHC 7.10.1 :
class Applicative m => Monad m where
...
    return      :: a -> m a
    return      = pure
...
-- оставили как было (по социальным причинам :)
--  (>>) :: forall a b. m a -> m b -> m b
--  (>>) = (*>)
...
https://hackage.haskell.org/package/base-4.8.0.0/candidate/docs/src/GHC-Base.html#Monad
deniok: (typed lambda)
2015-03-26 09:28 pm

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

Циклическую ротацию списка влево
> rotate 3 [1..10]
[4,5,6,7,8,9,10,1,2,3]
легко определить, используя take и drop:
> let rotate n xs = drop n xs ++ take n xs
Если напустить на это дело pointfree, он даст безумное:
rotate = ap (ap . ((++) .) . drop) take


Можете ли вы написать полностью бесточечную реализацию rotate, сцепив take и drop ровно одной стандартной библиотечной функцией?