ухмыляюсь

Порядочность бета-редукции

(1) Является ли отношение многошаговой бета-редукции на термах бестипового лямбда-исчисления отношением порядка? Докажите или приведите контрпример.

(2) Верен ли ваш ответ для просто типизированной лямбды?

Originally posted at http://deniok.dreamwidth.org/65363.html.
ухмыляюсь

про ЖЖ

Не читал (дальше первого абзаца) и не подписывал ТОС. Путин и Медведев должны уйти в отставку, после всего, что наворотили за последние 5 лет, а репрессивное законодательство отменено, чем скорее тем лучше. Писать здесь (в ЖЖ) не буду и транслировать тоже, через некоторое время журнал удалю. Образовательный и прочий контент из ЖЖ скопирован на dreamwidth.org. Всем привет.
Originally posted at http://deniok.dreamwidth.org/65165.html. Feel free to comment here or there.
ухмыляюсь

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

Инхабитация 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)
(Те, кто вызывает джинна, заведомо считаются проигравшими.)

Originally posted at http://deniok.dreamwidth.org/64820.html. Feel free to comment here or there.
ухмыляюсь

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

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

( Collapse )
ухмыляюсь

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)
ухмыляюсь

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

Часто парсеры пишут в виде, допускающем разбор неоднозначных грамматик 
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, конечно, еще потребуется, но тут, надеюсь, все справятся.)
ухмыляюсь

Предвыборное

Originally posted by edwardahirsch at Предвыборное
Если что, в воскресенье я собираюсь придти и проголосовать за Яблоко и яблочных депутатов всеми четырьмя бюллетенями.

Начало федерального списка у них неплохое, и никакой агитации за других разумных кандидатов я не видел. Ну, и вообще, яблочный год и время собирать камни.

Чего и вам желаю.
ухмыляюсь

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

В стандартной библиотеке (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) и современное, элегантно выпрямляющее кривизну кривого.
ухмыляюсь

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

... и педантично выровнял: 
($)    ::                      (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