skiminok: (xkcd)
Хозяйке на заметку: красивая проверка любой последовательности на отсортированность в одну строку. За O(N), между прочим. Ленивое, между прочим.


  let sorted xs = Seq.forall id <| seq { for (a, b) in Seq.pairwise xs -> a <= b }

skiminok: (xkcd)
Тут сегодня некто решил перевести на Хабре скучный пост с перечислением фич нового контейнера SortedSet<T> из .NET 4.0. Увидел я его только к вечеру, поскольку весь день мотался по городу. Пролистнул, ничего особенного вроде не обнаружил (в конце концов, что я не знаю про их дерево и его внешний интерфейс?), хотел было уже закрывать, как тут глаз зацепился за название метода GetViewBetween.

Видимо, когда я сразу после выхода .NET 4 просматривал спеки MSDN, я его как-то картинно и красиво прое не заметил. Полез в документацию. Совершенно не в стиле MSDN: капитанское описание цели метода (спасибо, я это и так уже знаю!), пример кода и ни слова о сложности алгоритма. Ладно, будем действовать самостоятельно.

Ценная строчка в документации указала, что класс хранится в сборке System.dll. Лезем в папку с фреймворком, открываем сборку Рефлектором, прокручиваем до нужного класса и нужного метода. Далее - серия code snippet`ов: как я в поисках истинной реализации прыгал от метода к методу:

public virtual SortedSet<T> GetViewBetween(T lowerValue, T upperValue)
{
    if (this.Comparer.Compare(lowerValue, upperValue) > 0)
    {
        throw new ArgumentException("lowerBound is greater than upperBound");
    }
    return new TreeSubSet<T>((SortedSet<T>) this, lowerValue, upperValue, true, true);
}


public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive) : base(Underlying.Comparer)
{
    this.underlying = Underlying;
    this.min = Min;
    this.max = Max;
    this.lBoundActive = lowerBoundActive;
    this.uBoundActive = upperBoundActive;
    base.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    base.count = 0;
    base.version = -1;
    this.VersionCheckImpl();
}


internal Node<T> FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive)
{
    Node<T> root = this.root;
    while (root != null)
    {
        if (lowerBoundActive && (this.comparer.Compare(from, root.Item) > 0))
        {
            root = root.Right;
        }
        else
        {
            if (upperBoundActive && (this.comparer.Compare(to, root.Item) < 0))
            {
                root = root.Left;
                continue;
            }
            return root;
        }
    }
    return null;
}
 


Все, приехали. Очевидный проход по дереву за O(H). Поскольку дерево у них там внутри сбалансированное (красно-черное, если конкретнее) - за O(log N).

Подводя итоги: неужели я таки дожил до этого священного дня, когда в стандартной библиотеке .NET появился lower_bound на set`ах? Учитывая, что BigInteger там тоже уже имеется, остается только пожелать для полного счастья next_permutation. Ну и какой-нибудь там nth_element на закуску.

Только вот ведь блин, нет этого .NET 4 нигде. Ни на одном контесте :(
skiminok: (xkcd)
Декартово произведение произвольного числа последовательностей на F#. Красиво.

let product seqs =

    List.rev seqs

    |> List.fold

       (fun acc cur ->

           [for seq in acc do

               for item in cur do

                   yield item::seq])

       [List.empty]



Здесь использованы: пайплайны, свертка и list comprehensions. А также элементарное индуктивное определение декартова произведения.
skiminok: (Compas)
Все-таки есть в жизни справедливость.
После х-надцатого коллективного возмущения сишарперов на форум TopCoder вылез добрый админ и пообещал удариться птицей оземь, но за несколько недель таки организовать на сервере свежий .NET. Как минимум 3.5, а там, глядишь, и на 4.0 уломают.
Спасибо тебе, мил человек. Здрав буди.
skiminok: (Compas)
В преддверии Google Code Jam 2010 решил поэкспериментировать, а как на F# пишутся короткие тулзы для простых задач. В соревнованиях такого уровня часто удобно использовать как минимум два языка: один типа Питона или любого другого скриптового - для коротких и простых задач, где важна скорость кодинга, и второй типа С++/C#/Java - для серьезных вычислений. В прошлом году я все писал на C#, а сейчас решил, что овчинка часто не стоит выделки.

Результат приятно удивил - действительно просто, быстро и удобно.
Вот код задачи А из прошлогоднего Qualification:

open System

open System.IO

open System.Text.RegularExpressions

 

let codeJam =

    use reader = new StreamReader("A.in")

    use writer = new StreamWriter("A.out")

    let readLine _ = reader.ReadLine()

 

    let matches regex s = Regex.IsMatch(s, regex)

    let countWhere p = List.filter p >> List.length

 

    let line = reader.ReadLine().Split(' ')

    let D, N = int line.[1], int line.[2]

    let words = List.init D readLine

 

    List.init N readLine

    |> List.map (fun s -> s.Replace('(', '[').Replace(')', ']'))

    |> List.map (fun re -> countWhere (matches re) words)

    |> List.iteri (fun i ans -> writer.WriteLine("Case #{0}: {1}", i+1, ans))

skiminok: (xkcd)
Всем читателям, кто еще не знаком, рекомендую замечательный блог Эрика Липперта — одного из главных разработчиков компилятора Microsoft Visual C# и собственно стандарта языка C#. (У кого напряги с инглишем — есть русский перевод, правда, он тормозит на три месяца =).

Так вот, по поводу функционального программирования, теории категорий, и всей этой динамической опердени =) Есть в этом блоге пост о различиях между ковариантностью и совместимостью по присваиванию. Пост сам по себе довольно интересен, но особенно умилителен постскриптум (для тех, кто шарит тему или просто честно прочел пост целиком):

UPDATE: My close personal friend (and fellow computer geek) Jen notes that in the Twilight series of novels, the so-called "werewolves" (who are not transformed by the full moon and therefore not actually werewolves) maintain their rigid social ordering in both wolf and human form; the projection from human to wolf is covariant in the social-ordering relation. She also notes that in high school, programming language geeks are at the bottom of the social order, but the projection to adulthood catapults them to the top of the social order, and therefore, growing up is contravariant. I am somewhat skeptical of the latter claim; the former, I'll take your word for it. I suppose the question of how social order works amongst teenage werewolves who are computer geeks is a subject for additional research. Thanks Jen!

Вот так концепции ФП незаметно втираются в нашу повседневную жизнь. Да, девочкам-фанаточкам Сумерок — привет ;)

FP |> OOP

Tuesday, 2 February 2010 01:31
skiminok: (xkcd)
В дополнение к предыдущему посту.

Двумя главными преимуществами таких простых пайплайнов адепты F# называют:
а) Автоматический вывод типов, действующий слева направо, что позволяет при использовании x |> someExpression писать в выражении someExpression поля и методы x (такие как x.Smth), если тип х уже был известен.
Так, если есть последовательность FileInfo, то если попытаться из каждого ее элемента выделить только имя файла таким макаром:
let getNames (myFileInfos: FileInfo seq)  =
  Seq.map (fun x -> x.Name) myFileInfos

то компилятор заругается, поскольку при обработке лямбды он понятия не имеет, какой тип может иметь ее входящий параметр, определить этого не может, и совершенно не верит, что этот параметр в общем случае имеет свойство Name.
Ситуация в корне меняется с применением пайплайна:
let getNames (myFileInfos: FileInfo seq)  =
  myFileInfos |> Seq.map (fun x -> x.Name)

Здесь, благодаря обработке слева направо, тип элемента последовательности уже строго определен на момент описания лямбды, и компилятор это скушает, еще и облизнется.

б) Второе преимущество вытекает из первого: возможность переделки нагруженных скобками ОО-выражений с вызовами методов удобочитаемыми и простыми последовательностями функциональных вызовов.
К примеру, в своем проекте-песочнице, где я набиваю разные заковыристые функции на F# по мере чтения "Expert F#" и тематических блогов, результаты всех функций отображаются в простом окошке WPF. Примерно так:
let test (textBox: RichTextBox) number answer =
    let run x = Run(x)
    let bold x = Bold(x)
    let paragraph x = Paragraph(x)
    let add x = textBox.Document.Blocks.Add(x)
    number |> sprintf "Testcase %d:" |> run |> bold |> paragraph |> add
    answer |> sprintf "%A" |> run |> paragraph |> add


А теперь сравните с вот этой прелестью, сильно смахивающей на Лисп:
let test (textBox: RichTextBox) number answer =
    textBox.Document.Blocks.Add(Paragraph(Bold(Run(sprintf "Testcase %d:" number))))
    textBox.Document.Blocks.Add(Paragraph(Run(sprintf "%A" answer)))

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

Вообще-то, оба аргумента покрывают одну и ту же проблему: функции F# и методы .NET, на котором оно построено, имеют разную природу, синтаксис вызова и парадигму. И потому при переходе из одного мира в другой, и обратно, приходится порою чесать себе затылок.

"Запад есть запад, Восток есть Восток, и им не сойтись никогда". ©
skiminok: (xkcd)
Рецепт успеха от Скима:

Откройте мой предыдущий пост.
Разместите данный и предыдущий посты рядом друг с другом (в этом весьма помогут двухпанельник, тайловый оконный менеджер, или просто система прилипания к краям, подобная Windows 7).
Читайте параллельно оба поста: код и его словесную интерпретацию.

...И попробуйте после этого сказать, что функциональные языки неудобочитаемы! =)

Под кат! )
skiminok: (xkcd)
Этим вечером я, будучи очень начинающим функциональщиком, чисто тренировки ради решил написать на F# эмулятор машины Тьюринга. Что интересно, получается это замечательно просто. Из всего сделал такие выводы:

1. Читабельность ФП-кода (как для непосвященного, так и для кодера) намного выше писабельности. Скорее всего потому что он выглядит почти как обыкновенная книга по математике на английском языке.
2. Когда пишешь ФП-код, периодически приходится сразу заботиться о производительности. Панацеей становится хвостовая рекурсия и хорошее владение функциональными структурами данных или методами, которые позволяют их эмулировать. Ил и забить на чистоту и юзать массивы :)
Но в моем случае я как честный человек писал тренировку, поэтому к массивам не прикасался, зато придумал для эмулятора удобный способ такой же сложности доступа к ячейке. В сущности, это сделало код еще более похожим на математическое определении конфигурации МТ.
3. Конкретно язык F# обладает одной занятной особенностью: он перенасыщен языковыми конструкциями для особых случаев. В отличие от любого другого ЯП, который я учил в своей жизни, здесь уже через несколько дней начинаешь путаться. Потом все потихоньку утрясается, конечно, но осадок остается.
4. Паттерн-матчинг — таки мощь :)

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

Исходный код )

(no subject)

Saturday, 12 December 2009 22:20
skiminok: (Default)
http://lorgonblog.spaces.live.com
Много, много F#.
Особенно впечатляют 8 статей про тот самый пресловутый катаморфизм (вот начало). Вечерком в субботу — самое оно для мозга =)

P.S. [livejournal.com profile] sofigenr, рекомендую! ;-)
skiminok: (Compas)
За последнюю неделю ваш покорный слуга успел побывать на семинаре Тимошенко "Введение в специальность", на вводной встречей OSUM для ИПСА, на тусовке IT-JAM и, наконец, на очередном Microsoft Developer's Day, на этот раз посвященном PDC2009. Говоря по-хорошему, о каждом из этих ивентов стоило бы рассказать поподробнее, а принимая во внимание их масштаб и количество интересной информации, как минимум тройка интересных записей из этого дела и получилась бы.

Но, честно говоря, лишних двух часов на набивание в блог всех моих впечатлений от этих ивентов у меня пока что нету. Поэтому не обессудьте: будем ждать ближайшего приступа вдохновения :)

А пока этого поста в блоге не видится, Ским, продолжающий терзать глубины функционального программирования, отыскал на просторах Хабрахабра статью про катаморфизм в F#.

Черт возьми, это же так красиво. И действительно так просто:

let FoldTree treeF leafV tree =
    let rec loop tree cont =
        match tree with
        | Node (val, left, right) -> loop left (fun lacc ->
                           loop right (fun racc ->
                           cont (treeF val lacc racc)))
        | Leaf -> cont leafV
    loop tree (fun x -> x)
skiminok: (Default)
Вторник, 8 декабря 2009.
Киевский офис компании Microsoft.
Четыре доклада по темам последнего PDC: Silverlight, Team System, SharePoint, параллельное программирование.
Регистрироваться здесь
Кто со мной?
skiminok: (Default)
«Однако вложение обычно является способом выразить включение (containment). Другими словами, если вы видите элемент Button внутри элемента Grid, ваш пользовательский интерфейс, вероятно, включает Grid, содержащий внутри себя Button».


UPD: Раскрываю все секреты =)
Книга не об ООП. Это «Windows Presentation Foundation в .NET 3.5 с примерами на C# 2008 для профессионалов» Мэтью Мак-Дональда, переведённая издательством "Вильямс".
Приведенная цитата встретилась мне в разделе, описывающем общую структуру XAML. Там говорится, что если один XML-тэг в XAML-документе вложен в другой, то скорее всего, такая конструкция выражает включение, то есть в интерфейсе один контрол находится непосредственно внутри другого.
Но на русском языке реплика звучит совершенно идиотски =)
skiminok: (Default)
В понедельник Microsoft сообщила о приобретении Teamprise - части SourceGear, что позволит улучшить кросс платформенную интеграцию Visual Studio.
Финансовая сторона сделки не разглашается.

Teamprise работает над тем, чтобы обеспечить работу Visual Studio на операционных системах, отличных от Windows: Unix, Linux и Mac OSX прямо из Eclipse. Как заявляет Microsoft в анонсе, функционал Teamprise будет интегрирован в Visual Studio 2010.

© LOR
skiminok: (Default)
Привет всему честному люду. Давайте я дам вам краткую подборочку событий за тот месяц, пока я был слишком занят, чтобы писать в свой ЖЖ.

Через неделю выходит на свет божий RAD Studio 2010. Я не знаю, буду ли я делать её полный обзор, как год назад, но если буду — то как минимум после того как загружу, установлю на свою машину и опробую все своими руками. А также почитаю справку.
По крайней мере, если судить по delphifeeds.com, то количество удобных возможностей опять впечатляет и опять дает робкую надежду на долгую и безоблачную жизнь прекрасному языку программирования.
Как минимум у нас есть RTTI уровня дотнетовского отражения, атрибуты, кастинг интерфейсов в объекты, улучшенная во много раз IDE, дебаг-визуалиаторы, поддержка естественного ввода (тачей и жестов) в VCL, Firebird, SOAP 1.2, JSON и множество разных мелочей.

Наша дружная квиповская команда совместными усилиями родила долгожданную статью на Хабрахабр: QIP: точки над "i". Целью было наконец-то объяснить всем негодующим, что творится за кулисами Инфиума, ситуацию, сложившуюся вокруг проекта, развенчать несколько оригинальных мифов и помочь тем, кто проект ненавидит. Знаете, получилось. Мы собрали такой холивар и собрание вопросов в комментариях, какой встречается на ресурсе не так уж часто. И, судя по всему, все-таки обратили мнение о программе к лучшему не у одного человека. Приятно это, когда правду можно говорить открыто, и эта правда помогает любимому проекту...
На очереди, наверное, мануал по плагонаписанию. Я давно думал что-нибудь подобное вкратце рассказать для населения.

Вообще я продолжаю увлекаться Хабрахабром. Да, конечно, Хабр уже не торт, но он продолжает оставаться:
  • ценнейшим ресурсом IT-новостей
  • отличным сборником пользовательского мнения
  • хорошей коллекцией познавательных статей по программированию
  • неплохим местом для заведения полезных и хороших знакомых

Так что будем продолжать писать. Это полезно, где бы то ни было.

Вот, к примеру, именно с Хабра я узнал о Киевском Coffee'n'Code. Думал пойти еще на первый, но его темы в итоге скатились в полный Веб и обсуждение вебдевовских фреймворков, к которым я не имею никакого отношения. Зато вот второй, судя по всему, очень даже заинтересует. Главное — чтобы никакая гадость (вроде вуза) не перебила поездку.

Работаю над PluginUpdater`ом. Сказать, что он сырой — не сказать ничего. Он икает, дергается, иногда выставляет претензии, многое не умеет, часть умеет, но не так, как надо, а часть вообще умеет, а все желают, чтобы не умел =) Короче говоря, это совершенно не то состояние, в котором должен находиться софт подобного уровня. Поэтому я работаю судорожно, август заканчивается, а по опыту знаю: как только начнется вузовский семестр, моё свободное время начнёт улетучиваться просто с поразительной скоростью. И пока оно еще есть, надо много сделать. Итогом этого "много" и форумских споров стало то, что сегодня мне совершенно не хочется ничем заниматься, хотя туду разросся до галактических масштабов. Вот, поэтому сижу, пишу в блог...

Кстати, о блоге. Потратил полчаса, прошел по нему до самого зарождения и залочил самые экстравагантные записи, сделанные в период юного и беззаботного детства. Всего маразматичных, личных и смешных постов оказалось штук 20, остальные ещё можно показывать людям :) Когда читал некоторые — ржал до безумия, но таких меньшинство, в основном это те, которые просто не соответствуют тематике блога. Знания изменились, кардинально. А вот взгляды, что интересно, с тех пор остались практически те же.

Исполнил древнее желание — купил комбинацию APC-шных стабилизатора и ИБП. Потому что за всё лето, по-моему, так ни разу и не выключал компьютер самостоятельно: постоянно это было по вечерам из-за перебоев в электричестве. Спасибо тебе, наше дорогое Киевэнерго.
Зато теперь я по крайней мере могу не бояться, что однажды в солнечный и приятный вечер у меня полетит к чертям собачьим дневная работа.
А вообще, бекапы — наше всё.

У меня сейчас есть аккаунт на самых популярных сайтах по инвайтам: Хабрахабр, Дару~Дар, Демоноид, 0дей, Новафильм. Хорошие друзья, хорошая репутация и хорошие места дислокации многое решают. Проблема только в том, что на некоторых из них я не могу похвастаться активностью: всё-таки Волевские тарифы дают о себе знать. Ну нет в моём районе достойных домашних сетей, нет. А есть всем ненавистные Воля, ОГО, Билайн и дорогущие беспроводники. Придется пока что так и сидеть. Тем более что волевцы хитрые, они бонусами заманивают, скоростью, акционными временными анлимами, бесплатными ресурсами на своём DC. Ну что же, придется пока сидеть так.
По крайней мере Хабр и ДаруДар я облюбовал по полной программе)

Практически полностью перешёл на C#. На Делфи кодю плагины для Инфиума (человеческий перевод .NET SDK, который я пытался организовать, лежит пока в сторонке недописанным, к сожалению) и редкие просьбы друзей о мелких утилитах. Последние, кстати, тоже скоро буду делать на дотНете.
А уж Google Code Jam 2009 и подавно писать надо будет на шарпе. Только для него надо бы ещё какой-нибудь мелкий подручный скриптовый язык для быстрых задач. Пока изучаю потихоньку PowerShell, со всем остальным стаффом этого класса я как-то не дружу. В общем, посмотрим.

TopCoder. Четко осознал свою позицию: синий. То есть уровень — выше среднего участника, однако среди таких высших — худший. Что ж, я так и подозревал с самого начала.
До жёлтого я поднимусь, судя по всему, не раньше чем через полгода. А уж о красном можно только мечтать.
Потому что, как я однажды писал в статусе, «из этого человека никогда не выйдет хорошего олимпийца. Он умеет хорошо думать. Он умеет красиво писать. Теперь только научите его делать это БЫСТРО!»

Старый комп надо будет вытащить на свет божий из шкафа и приспособить к какому-то полезному делу. *Ага, в однокомнатной квартире...* Потому что считать себя особой, имеющей отношение к IT, и не разбираться должным образом в администрировании — бред собачий.

Резюмируя. Вообще, новостей много, как айтишных, так и не имеющих к ним отношения. Но описывать их все я попросту замонаюсь, поэтому закругляюсь. Тем более пора идти чем-то заниматься всё-таки. Пока возможности есть.
На сим плановое обновление блога считаю закрытым, до новых встреч.
С уважением, Skiminok.
skiminok: (Default)
Сессия наконец-то благополучно и вполне успешно закончилась, так что я снова возвращаюсь к собственному блогу, который забросил на два с лишним месяца, и публикую здесь запись о его поднятии из анабиоза =)

А ещё здесь отмечаю насущную проблему: мне нужно какое-нибудь дело, работа, проект, а то я сдохну от ничегонеделанья в ближайшие два месяца. В общем, в Киеве ищется работа (удалённая либо временный контракт) для junior-разработчика Delphi/C# либо технического копирайтера. Не самое длинное (я просто составил общую картину и любимые разработки), но все же дающее общее представление портфолио можно найти на Weblancer либо на Free-lance. Жаль, конечно, но фриланс-вакансии на тему прикладного программирования в настоящее время попадаются, как редкие жемчужины — а-ля «это было давно и неправда»...

Profile

skiminok: (Default)
skiminok

Most Popular Tags

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526272829 30
31      

Syndicate

RSS Atom