juan_gandhi: (Default)
 https://vpatryshev.wordpress.com/2017/01/20/three-popular-fp-myths-3/

More Haskell bashing.

"Haskell is so good that if a functor does not have a free monad, it cannot be written in Haskell". Which is funny. Something like Haskell version of Church thesis.
juan_gandhi: (VP)
https://arxiv.org/pdf/1611.09475.pdf

Domain-Specific Languages of Mathematics: Presenting
Mathematical Analysis Using Functional Programming
juan_gandhi: (VP)
монады в скале и все такое

Добавить/поправить/расширить что, или как?
juan_gandhi: (VP)
So, in Scala Lift, there's one single transaction per request. And I have to, say, process a thousand records, and then what? I thought about adding a request handler per record, and call it via http. Stupid, eh. There are actors. So I wrote the actor, moved all the functionality there, and now I call that actor. Can process that 1000 in parallel now, big deal. And each has its own transaction of course (just switch to Future).

  def process(lineNo: Int, line: String): Status = {
    importActor !? ((lineNo, line)) match {
      case s:Status => s
      case basura   => onError(lineNo, s"Wrong response from importer: $basura")
    }
  }


I know, it's rather stupid, but well... just having fun
juan_gandhi: (VP)
products and sums in categories

I wonder if you find something new for you there. Comments wholeheartedly welcome.
juan_gandhi: (VP)
Ребутнул свой presheaf.com, теперь порт 80 не работает. И вот это вот камлание не помогает:

sudo iptables -A INPUT -i eth0 -p tcp --dport 80 -j ACCEPT
sudo iptables -A INPUT -i eth0 -p tcp --dport 8080 -j ACCEPT
sudo iptables -A PREROUTING -t nat -i eth0 -p tcp --dport 80 -j REDIRECT --to-port 8080

дыбр

Oct. 24th, 2013 01:33 pm
juan_gandhi: (VP)
Вчера... вчера я где-то в полчетвёртого зафигачил новый парсер, запустил тесты на ночь на стейджинге, и в шестом часу ломанулся опять в город, на, блин, встречу категорщиков. До города-то доехал нормально, но в городе застрял на всяких там улицах. Да затрахало. Последний раз (в этом году). Заявился в офис Прези в 7:15, меня уже искали.

Ну офис ладно, мы проникли в конце концов; нас было шестеро в сумме. В комнате, куда мы пришли, на доске были остатки урока венгерского, и я обнаружил, что ха, на этом-то уровне mindent tudom. Должны были проходить третью главу книжечки Пирса - typed lambdas, categorical style. Ну и чо. Собралось опять половина новых; объясняй им, что за пределы такие... нет, что такое декартово произведение! И что за суммы такие! Короче, протрахались минут сорок с этой ерундой, потом как-то хитростью (без сопряженных функторов) протащили экспоненту.

Тут ещё новенький, Сергей, всё норовил возразить, в русском стиле, мол, нам эти ваши абстракции и даром не нать, у нас всё множества кругом, и можно ограничить дискурс малыми категориями - теория множеств, дескать, и есть основа вычислительных наук. На предложение охарактеризовать Cat было молчание. Я пытался добиться, какая польза вычислениям от аксиомы выбора. потом нарисовал пример неизмеримого подмножества отрезка [0,1]. Молчанье.

Ну ладно. Я уже совсем был почти pissed off. Плюс голодный; обещанной еды Прези не предоставило.

С божией и шахафовой помощью втянулись, наконец, в книжку. Дошли аж до примерно 20-й строки. Потом мне стали объяснять рулеса типовой лямбды; в частности, постоянно фигурировала какая-то гамма. У меня в книжке никакой гаммы не было, и я стал приставать, откуда взялась эта невидимая гамма.

И тут оказалось, что гамма невидима только у меня в книжке, а у остальных в книжке гамма есть. Пришлось мне руками вписывать гамму!

После чего Мэтью пошел к доске и стал расписывать смысл в общем-то простых рулесов. Но Мэтью тоже из Израиля, и гамму он писал как её писали финикийцы, в обратную сторону (гимель, ); ну чо.

Я же как этот стал приябываться к каждому рулесу. Ну типа вот вы говорите, что x имеет тип A × B - а это ж изоморфно B &time; A, так оно имеет и этот тип? Или чо? Или как?

Меня долго убеждали, что тип парсится в процессе валидации фразы, и определяется однозначно, но тут я совсем озверел - как вы нахер определите однозначно, если пределы в категории, как и вообще все сопряженные, определены с точностью до изоморфизма? Это же бред, почему unit имеет тип Unit, а не UnitUnit × UnitX?

И тут Шахаф сказал.

Дык. Для этого Воеводский HoTT и впендюрил, что типы не однозначно, а с точностью до изоморфизма определяются.

О блин. Мы вышли на гомотопическую дорожку. Уже Дан Пипони книжку читает, и ещё кто-то там в Гугле. Короче, надо всё бросать и переучиваться заново. Потому что у Пирса в третьей главе булшит. И что, никто не видел? Тьфу.

Ну и вот, и был уже десятый час, и я сказал всё, у меня завтра в 7 класс, пора. Подцепил Мэтью и Шахафа, потому что блин я ценю каждый момент когда можно поговорить с умным человеком, а Шахаф просто блистает. Он скромен до ужаса, но вот с кем бы я работал.

И вот едем мы, я какую-то музычку по радио поставил, и обсуждаем какую-то хрень ну типа как бы нам перекатиться с семинаром в Заливную, желательно в Маунтин Вью (и другого Мэтью ещё притащить - тоже израильтянин); и с Валерией да с Дэном согласовать, чтоб всем удобно было.

И тут Шахаф говорит - а, а кстати, в хаскеле все монады происходят от карриинга.

Чо?! О блин! Вот чо! Это же representable functors! Главное - пределы сохранять.

Перевариваю.

Ну и заодно, к слову, посмотрел как Максим жжет глаголом на киевском fprog:

http://www.youtube.com/watch?v=lJlqQDMpY3I&feature=youtu.be&a

Ну как мы уже поняли, всё не так просто. Но и не так уж запрещено.
juan_gandhi: (VP)
Extracting PDF from Mozilla Browser - and Doing it Nicely

That's a detailed account of the thing I already posted a couple of days ago. And what I'm enjoying here is Functional Programming. I don't know why Stroustrup does not know that it works. Worked for me. :p
juan_gandhi: (VP)
  def downloadPDF(url: String): Result[(File, String)] = {
    loadPage(url) andThen
    waitForSelector("div.textLayer") andThen 
    runJS("return extractPdfContent()") andThen {
      Thread.sleep(1000) // give browser a chance
      val extracted = runJS("return intBuf2hex(extractedPdf)") map (_.toString)
      val pdf = extracted flatMap 
        (_.decodeHex #> File.createTempFile("download", ".pdf"))
      
      val html = runJS("return _$('div.textLayer').innerHTML") map (_.toString)
      pdf <*> html
    }
  }


What happens here.
I load a page in Mozilla, via Selenium. Actually a pdf, but Mozilla pretends it's html.
andThen... (meaning, if it failed, no need to proceed, right?)
Then I extract innerHTML of the content div, I need to parse it.
Oh, the _.js means we convert the value of this string into a Javascript representation of the string, with apos escaped, wrapped in apos.
But what the server sent is actually a pdf (rendered in Mozilla by pdf.js);
So I need the pdf binary. It was https, and there's no api for interception.
So I go into the guts of pdf.js, find the holder of the binary, and tell it to give me the bytes (in a continuation). But the whole communication with the browser is imperative; so I sleep for a second. No biggie.

When I wake up, the bytes I need are already pulled from pdf.js future and converted to a hex string (like 160k of text, one line).
I extract it from the browser.
Then I decode the hexes, producing bytes, and send them to a temp file; the #> op returns the file... actually, monadically, a hope for a file.
There's flatMap here; we flatten all hopes within hopes into one big hope - or an explanation of why everything fell apart.

Now we have, hopefully, a text, and, hopefully, a pdf. We apply tensor product to produce either a long list of explanations why we failed, or a tuple, a pair (text, file).
QED.

Questions? Obvious?
juan_gandhi: (VP)
"Note bene: this is bleeding edge thinking!"

And I wonder, can it be translated into, say, a regular language? Or we should learn something instead?
juan_gandhi: (VP)
Вчера в кинотеатре посёлка Пало Альто ("Большое Палко") была встреча избирателей энтузиастов с Бьярне Строуструпом, профессором из Техаса. Бьярне известен тем, что придумал язык си++, за что ему, конечно, мир благодарен.

Я там озирался затравленно, ни одной знакомой рожи. Ну ладно, Джон Калб. Ну в смысле и сильно потолстевший Степанов, конечно; но я имею в виду взаимно знакомых.

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

Вообще-то речь шла о С++11, и он показывал новые фичи, лямбды и что-то вроде имплиситов, можно прям написать 11hours+20minutes+40seconds и оно поймёт. Почти как на скале. Только у си своя магия (и меньше мусора). Довольно славно фьючерсы можно использовать - но можно прямо из лямбды менять полуглобальную переменную - если вам "так удобнее" (в смысле, если вы ничему не учились, или учились, но ничему не научились).

У меня разрядился лаптоп, и я сидел развесив уши. Радовался за прогресс си, и недоумевал, хм, лямбды есть, тайпклассы есть (почти), а где монады? Или потому что тайпклассов нет, так и функторы с монадами рано вводить?

В конце лекции я и спросил его, а что, вот у вас уже и лямбды и концепты, уже, может быть, пора вводить монады и cps, тем более, что лямбды-то уже есть. И тут Бьярне, не особо зацепившись за концепты (которые, говорят, не включены в стандарт), сообщил, что фп все лузеры, и "мы не знаем, почему фп провалилось"; тут же добавил, что на самом деле сишный народ не поймёт. Знакомые речи, Джош Блок тоже говорил, что джавщик не способен понять лямбды, поэтому лямбды не нать. Не треба. Музыка должна быть напевной (это товарищ Жданов говорил гражданину Шостаковичу и господину Прокофьеву).

Следующим вопросом было что-то про концепты, потом про лямбды... короче, собравшимся была пофиг эта вся ваша ручная оптимизация, закат солнца вручную, а хотелось чего-то уже из 21-го века.

Чёс языками как-то быстро закончился, и все стали расходиться. Я хотел было пойти к Степанову, он же всё-таки как бы алгебраист, и спросить, он-то что думает о ментальном застое в головах и о внедрении монад, но потом подумал, ну что я буду троллить прямо при живом Бьярне рядом; бог с ними.

Ну и тем более Джон Бруер и Стив Ганц тут же вертелись, и мы стали чесать языками про аппликативные функторы, потом пошли со Стивеном в Титайм пить Russian Caravan и вкушать cheese platter (пока мой компьютер заряжается).

Но главное я вынес. Вся эта дурь с delete[], buffer overflow, memory leaks, она вызвана тем, что монадические действия выполняются как будто у нас тут чистые функции. Вместо >>= употребляют ;

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


Он использовал ресурсы вне монадного контекста.
juan_gandhi: (VP)
I believe we can.

Generally speaking, say, we have two monads, T and U; their composition T ∘ U is a functor which is not always a monad. Unit is okay, but multiplication, T ∘ U ∘ T ∘ U → T ∘ U does not always exist. It would exist if the two monads commuted, that if, if we had U ∘ T → T ∘ U, which is also known as traversal of U over T; in case U comes from a monoid, this is the famouse "map/reduce".

I was working on a simple example in Java programming language, say, take Reader monad and Maybe monad, the latter also known as Option in Scala and in various Java libraries. It is almost obvious that if we have a Maybe wrapped into a Reader, it cannot be naturally transformed into Reader wrapped into a Maybe.

Maybe in Java can be thought of as a function that may throw some kind of exception, and we don't care which, just catch it (and log it, that's what Java people do with exceptions).

Reader in Java can be represented as "dependency injection" - we have a function that is supposed to return something, but its behavior depends on some external circumstances unknown to client code. This is different from State, an example of which is a Random Numbers Generator; with "dependency" we are tied to the same environment during the lifetime of the program.

For the utmost simplicity, let's imagine that we have only two possible "environment values", say, DEBUG, which is either TRUE or FALSE.

So, in this case, what the client thinks of as a function: X → Y, in our Reader is actually a function: X → Y2 whereby we potentially produce two values, one for DEBUG=TRUE and another for DEBUG=FALSE.

If we deal with Maybe, what a client sees as a function: X → Y is actually function: X → 1+Y, where failures map values into this 1, which in Java is represented via null.

Okay.

Now one composition is (1 + Y)2 == 1 + 2×Y + Y2, and the other is 1 + Y2.

We can easily embed the second one into the first one, but there's no general natural way to transform the first one to the second one; what will we do with the two instances of 1×Y? Unless we have Y as an algebra over Maybe, that is, a natural transformation 1 → Y.

Nevertheless, I will show that the composition of Maybe ∘ Reader is a monad.

First, let's generalize Reader to a dependency on a certain type E of "environment: Reader<E>.

So, Reader amounts to having a functor X ↦ XE, where unit X → XE amounts to constant, and multiplication (XE)E → XE is dual to diagonal Δ E → E×E, that is, XΔ.

Now, can we naturally transform Reader(Maybe(Reader(Maybe(X)))) to Reader(Maybe(X))? Not only naturally, but with all the monadic properties of multiplication (unit and associativity, that is).

We have (1 + (1 + X)E)E, and we need to produce (1 + X)E

This is dual to (thanks to Yoneda Lemma) having a good transformation
E × (1 + (1 + X)E)E → (1 + X)

Let's throw in Δ E → E×E, and build
E × (1 + (1 + X)E)E → E × E × (1 + (1 + X)E)E → (1 + X)

Using eval: E × AE, have
E × E × (1 + (1 + X)E)E → E × (1 + (1 + X)E)

So it would be enough to have a good
E × (1 + (1 + X)E) → (1 + X)
which amounts to having

E × 1 + E × (1 + X)E) → (1 + X)

Which is obvious: the first component maps to 1, the second is eval again.

That's it.

Questions? Errors? Remarks? Suggestions.

(One question is how come Java types are not Maybe-algebras, they are, are not they?)
juan_gandhi: (Default)
Тут мы с [livejournal.com profile] sassa_nf обсуждали вопрос, как это получается, что оно монада.

В принципе, это есть в МакЛейне, но у МакЛейна всё так мудрено. А надо-то на пальцах.

В другом месте - т.наз. функторы Hom участвуют - а у меня к ним прямо гомофобия; такую неприязнь чувствую к функтору Hom, кушать не могу.

Так вот, напишу-ка я тут вкрадце, шо за сопряженные функторы и как они связаны с монадой.
Для программистов напишу, так что никаких когомологий, кобордизмов, 2-категорий, расширений Кана, а всё на пальцах, лишь бы не лень читать было.
Read more... )
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Весь нижеупомянутый код расположен на гитхабе у котят.

Пример. Моноид и Накопление Ошибок


Read more... )
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Весь нижеупомянутый код расположен на гитхабе у котят.

Пример. Traversable



Когда у нас есть аппликативный функтор, у нас имеется что-то вроде моноида: есть относительный синглтон (не буду вдаваться в подробности), pure, и есть бинарная операция <*>; с помощью этих двух операций мы можем устраивать свёртку, скажем, списка... ну или дерева, если есть такая возможность, распараллелить, как в map/reduce. trait Traversable как раз обобщает список и дерево - по нему можно итерировать аппликативный функтор.

А именно,
// T будет траверсабельным, если определены:
trait Traversable[T[_]] {
  // для аппликативного функтора app и функции f обход структуры as
  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(as: T[A]): F[T[B]]
  // и для, скажем, дерева аппликативов можно построить один аппликатив с деревом внутри
  def dist[B, F[_]](app: Applicative[F]) = traverse[F[B], B, F](app)(identity[F[B]]) _
}


Легко определить траверсабельность для списка:
implicit object TraversableList extends Traversable[List] {
  def cons[A](a: A)(as: List[A]): List[A] = a :: as

  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(al: List[A]): F[List[B]] = {
    al match {
      case Nil => app.pure(List[B]())
      case head :: tail => app.applicable(app.lift(cons[B] _) <@> f(head)) <*> traverse[A, B, F](app)(f)(tail)
    }
  }
}


Тут как бы всё очевидно - если список пустой, то применяем pure, а иначе сканируем весь список, применяя последовательно <*>.

Аналогично поступим и с деревом, только сначала надо как следует определить дерево.

trait Tree[T]
case class Leaf[T](t: T) extends Tree[T]
def leaf[T](t: T): Tree[T] = Leaf(t)
case class Node[T](left: Tree[T], right: Tree[T]) extends Tree[T]
def node[T](left: Tree[T])(right: Tree[T]): Tree[T] = Node(left, right)


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

Вот как определяется траверс на таких деревьях:

implicit object TraversableTree extends Traversable[Tree] {

  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(at: Tree[A]): F[Tree[B]] = at match {

    case Leaf(a) => app.lift(leaf[B]) <@> f(a)
    case Node(left, right) => {
      implicit def applicable[A, B](tf: F[A => B]) = app.applicable(tf)

      val traverse1: (Tree[A]) => F[Tree[B]] = traverse(app)(f)

      app.pure(node[B] _) <*> traverse1(left) <*> traverse1(right)
    }
  }
}


Обычное дело в Скале - пришлось ввести промежуточную переменную, traverse1, а то Скала в типах запутается. И так всё сложно.

Надо заметить, что не всякий функтор траверсабелен - например, функтор Env, попробуйте-ка его траверсировать с помощью Maybe - это было бы равносильно получению тотальной функции из частичной. Good luck.

Ну а теперь примеры траверса.

Список:
import TraversableList._

val distributor = dist[String, Set](AppSet)
val setOfLists = distributor(List(Set("a", "b"), Set("x", "y")))
setOfLists must_== Set(List("a", "x"), List("a", "y"), List("b", "x"), List("b", "y"))


Дерево:
import TraversableTree._

val distributor = dist[String, List](AppList)
val treeOfLists:Tree[List[String]] = Node(Leaf(List("a", "b")), Node(Leaf(List("x", "y", "z")), Leaf(List("1"))))
val listOfTrees = distributor(treeOfLists)
def tree(s: String) = Node(Leaf("" + s(0)), Node(Leaf("" + s(1)), Leaf("" + s(2))))
listOfTrees must_== List(tree("ax1"), tree("ay1"), tree("az1"), tree("bx1"), tree("by1"), tree("bz1"))


В следующей части - моноиды, и траверс с моноидами.

Profile

juan_gandhi: (Default)
juan_gandhi

March 2017

S M T W T F S
    1 2 3 4
5 6 7 8 9 1011
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 293031 

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Mar. 29th, 2017 09:07 pm
Powered by Dreamwidth Studios