deniok | Entries tagged with сборник задач и упражнений по хаскелю

Как известно композиция двух функторов является функтором, причем fmap для этой композиции - это композиция fmap'ов:

GHCi> (fmap . fmap) (^2) [Just 3,Just 5,Nothing]
[Just 9,Just 25,Nothing]

Левый fmap протаскивает свой аргумент (fmap (^2)) через конструкторы списка, а дальше оставшийся fmap протаскивает свой аргумент (^2) через конструкторы Maybe.

( а фолды? траверсы? аппликативы? монады?... )

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, конечно, еще потребуется, но тут, надеюсь, все справятся.)

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

В выражении

GHCi> succ <$> "abc"
"bcd"

оператор <$> имеет тип (Char -> Char) -> [Char] -> [Char]. Верно ли это утверждение для обоих вхождений <$> в следующем выражении

GHCi> succ <$> succ <$> "abc"
"cde"

Приведите пример таких объявлений типа данных с конструктором данных T и сигнатуры функции f, что реализация

f (T x) = T x

проходила бы проверку типов, a

f x = x

нет.

Маленький хаскеллист попал в Зазеркалье и, преодолев неисчислимые препятствия, дошел до последней горизонтали. Белая и Черная Королевы говорят, что для того, чтобы стать SPJ, ему нужно пройти «Королевский экзамен», ответив на Черный и Белый вопросы: всякий ли Functor является Rotcnuf? всякий ли Rotcnuf является Functor?

class Rotcnuf f where
  mfap :: f (a -> b) -> a -> f b

Помогите маленькому хаскеллисту стать SPJ.

Как вам скорее всего известно, написать представителя класса типов 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

Объясните, почему невозможно по представителю Foldable для конструктора типа сгенерировать представителя Traversable.

Как известно seq вычисляет свой первый аргумент до слабой заголовочной нормальной формы (WHNF). Не пользуясь GHCi, ответьте на вопрос, каково будет значение следующего выражения

Prelude> (\True y -> ()) False `seq` 5

Проверьте себя в GHCi. Какова будет полученная в первом аргументе seq WHNF?

UPD. А теперь вопрос на засыпку: каково будет значение следующего выражения

Prelude> (\True -> \y -> ()) False `seq` 5

Считаете ли вы это правильным?

Циклическую ротацию списка влево

> 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 ровно одной стандартной библиотечной функцией?

Мы привыкли, что правая свертка (foldr) хорошо заточена для работы с бесконечными списками:

> let mapPlusPi = foldr (\x xs -> (x+pi):xs) []
> head $ mapPlusPi [1..]
4.141592653589793

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

> let evenOnly = snd . foldr (\x (os,es) -> (x:es,os)) ([],[])
> evenOnly [1..10]
[2,4,6,8,10]

Только вот на бесконечном списке она ведет себя неподобающе

> head $ evenOnly [1..]
Interrupted.

Почему это происходит, и какие минимальные изменения можно в нее внести, чтобы восстановить утраченную работоспособность?

Доказать, используя Хаскель, что следующие тавтологии верны интуиционистски

(a -> c) /\ (b -> c) -> a \/ b -> c
(a \/ b -> c) -> (a -> c) /\ (b -> c)

(Понятно, что конъюнкция - это пара, а дизъюнкция - Either.)

UPD. Стоит напомнить, что изоморфизм Карри-Говарда имеет место между интуиционистской версией пропозициональной логики и подмножеством Хаскеля без рекурсии. То есть использовать рекурсию нельзя - ни явно, ни неявно. Ну и определение отрицания требует в Хаскелле некоторых хаков, но при доказательстве этих формул оно не требуется.

Хорошая хотя и простая задачка возникла в процессе проверки домашних заданий. Чем отличается поведение следующих двух функций, и в чем причина такого отличия:

diff xs = do
    p <- zip xs (tail xs)
    return $ abs (fst p - snd p)

diff' xs = do
    p <- zip (tail xs) xs
    return $ abs (fst p - snd p)

К завтрашнему занятию задачку со звёздочкой сделал, а то некоторые больно умные последние 15 минут практики бьют баклуши, решив всё заданное.

Введём следующий трёхпараметрический типовый оператор, инкапсулирующий композицию однопараметрических конструкторов типов:

newtype Compose f g x = Compose {getCompose :: f (g x)}

Каков кайнд этого конструктора типов? Приведите пример замкнутого типа, сконструированного с помощью Compose, и пример терма этого типа.

Определите функцию

ffmap h = getCompose . fmap h . Compose

и объясните её выведенный тип. Попробуйте осуществить вызов

> ffmap (+42) $ Just [1,2,3]

В чём причина ошибки?

Чтобы обеспечить работоспособность подобного вызова, сделайте тип Compose представителем класса типов Functor:

instance (Functor f, Functor g) => Functor (Compose f g) where
  fmap                =   ???

Проверьте работоспособность на примерах:

> ffmap (+42) $ Just [1,2,3]
Just [43,44,45]
> ffmap (+42) $ [Just 1,Just 2,Nothing]
[Just 43,Just 44,Nothing]

Сделайте тип Compose представителем класса типов Applicative:

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure               = ???
  (<*>)              = ???

Проверьте работоспособность на примерах:

> getCompose $ (+) <$> Compose [Just 1,Just 2] <*> Compose [Nothing,Just 40]
[Nothing,Just 41,Nothing,Just 42]
> getCompose $ (+) <$> Compose [Just 1,Just 2] <*> Compose [Just 30,Just 40]
[Just 31,Just 41,Just 32,Just 42]
> getCompose $ Compose [[(+1)],[(+2),(+3)]] <*> Compose [[10,20],[]]
[[11,21],[],[12,22,13,23],[]]

Crossposts: http://deni-ok.livejournal.com/51673.html

А вот, кстати, при проверке лямбда-калькуляторов, написанных студентами, возникла такая задачка.

Пускай мы реализовали на Хаскелле лямбда-термы

data Term = 
    Var String
  | App Term Term
  | Lam String Term

проверку их альфа-эквивалентности (можно и точное совпадение, для наших целей не важно):

alphaEq :: Term -> Term -> Bool

и одношаговую бета-редукцию (нормальную, для определенности, хотя это тоже не важно):

reduce :: Term -> Term

В последнем случае при отсутствии редексов просто возвращается исходный терм.

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

reduceToNF :: Term -> [Term]
reduceToNF = unfoldr step where 
  step t = 
      let next = reduсe t in 
    if t `alphaEq` next 
    then Nothing 
    else Just (t, next)

Не видите ли вы червоточины в этой схеме?

Crossposts: http://deni-ok.livejournal.com/51180.html

Сегодня на stackoverflow, отвечая на вопрос, Andreas Hammar привёл хорошие примеры. Сохраняю на будущее, как простые задачки для студентов

data    D a = D a
data    S a = S !a
newtype N a = N a

constD x (D y) = x
constS x (S y) = x
constN x (N y) = x

Какие из следующих вызовов завершат свою работу как Deep Thought, а какие как Earth?

D undefined `seq` 42
S undefined `seq` 42
N undefined `seq` 42
constD 42 undefined
constS 42 undefined
constN 42 undefined

Три задачки с экзамена, в порядке усложнения условия.

Написать замкнутый терм типа (a -> b) -> ((a -> b) -> b) -> b.

Написать замкнутый терм типа (a -> b) -> ((a -> b) -> b) -> b, которому нельзя приписать тип c -> (c -> b) -> b.

Написать замкнутый терм с наиболее общим типом (a -> b) -> ((a -> b) -> b) -> b.

Напишите представителя класса типов Applicative, для которого выполнялись бы законы Identity и Homomorphism:

pure id <*> u = u
pure u <*> pure x = pure (u x)

но не выполнялся бы законы Composition и/или Interchange:

pure (.) <*> u <*> v <*> x = u <*> (v <*> x)
u <*> pure x = pure ($ x) <*> u

UPD. Ну и по ходу дела возникли бонусные вопросы: написать такого представителя, чтобы не выполнялся (a) только Composition; (b) только Interchange.

Устно вычислите ~~значения~~ побочные эффекты выражений и проверьте результат в GHCi:

let x = print "first" in print "second"

let x = print "first" in x >> print "second"

(\x -> print "first") (print "second")

print "first" `seq` print "second"

(Значения тоже можете вычислить в качестве бонуса:)