deniok

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

Очень заманчивая идея о том, как в Agda загнать под капот навязчивые subst и cong. Пример от автора.

А вот подскажите, на 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.

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

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

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

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

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

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

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

Plan Foldable или Plan List?

Мы привыкли, что правая свертка (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. Стоит напомнить, что изоморфизм Карри-Говарда имеет место между интуиционистской версией пропозициональной логики и подмножеством Хаскеля без рекурсии. То есть использовать рекурсию нельзя - ни явно, ни неявно. Ну и определение отрицания требует в Хаскелле некоторых хаков, но при доказательстве этих формул оно не требуется.

Заказал на Озоне книжку Саймона Марлоу "Параллельное и конкурентное программирование на языке Haskell", переведенную уважаемым Виталием Брагилевским. Для рачительных и экономных сообщаю, что покупка на сайте издательства ДМК Пресс обойдется несколько дешевле.

Вот отзыв замечательного Романа Чепляки, правда на английскую версию.