дробные, отрицательные и мнимые типы

Недавно sassa_nf задал вопрос: как на Скале записать автомат, типа такого рекурсивного определения

  type State[A] = (A, A=>State[A])

В Скале всё немножко не так делается, и в книжке Steps in Scala написано, как это записать по-скальному

 case class Fix[F[_,_],α](out: F[α,Fix[F,α]])

Ну это обычаи Скалы, а можно и по-другому подойти. В октябре мы с Майклом Стеем беседовали на эту тему, и он говорит, а чё, у некоторых типы бывают не только отрицательные, а и мнимые.

Дык. Галуа-то зря, что ли, страдал на благо человечества?

Начнём со всем знакомых списков. Список, он ведь как определяется?

 List[T] = 1 + T × List[T] // здесь я перемешиваю очень разную нотацию, и скальную, и математическую

1 есть Nil, а × есть декартово произведение (по-программистски - образование пары, парообразование).

Ну типа список это или пустое, или пара, элемент и опять список.

Уравнение list(t) = 1 + t × list(t) решить несложно, ответ будет list(t) = 1 / (1 - t). Здесь мы совсем охуели - вычитаем тип из единицы, а потом делим единицу на эту разницу. А чё, мы ж понимаем, формальное расширение... да потом, всегда можно разложить в ряд Тейлора, и получить list(t) = 1 + t + t2 + t3 + ...
Ну это тип списка и есть, или он пустой, или один элемент, или два, и так далее, чо.

А теперь вернёмся к уравнению sassa_nf; напомню, что A => B - это степень, BA

state(t) = t × state(t)t

Чтоб это уравнение решать, надо взять логарифм.

  ls(t) =(def)= logt(state(t))
  ls(t) = 1 + ls(t) × t
  ls(t) = 1 + t + t2 + ...
  state(t) = t1+t+t2+...

А то и ещё проще, state(t) = list(t) => t

Мнимые типы нам тут не попались, но если взять уравнение для двоичного дерева,

  bintree(t) = 1 + t × bintree(t) × bintree(t)

То у нас как раз квадратное уравнение, да ещё и с комплексными корнями. Ну ничего страшного, мы ж понимаем. Когда-то древним людям и отрицательные числа казались порождением диавола (ну или там коварных ростовщиков).

Я как-то не углублялся в монадическую сущность списков и комонадическую (не уверен) этих автоматов. Не об этом сейчас речь, хотя в принципе-то речь об инициальной алгебре и терминальной коалгебре.

из всех жежистов меня больше всего поражает...

brother2

Seriously