skiminok: (!int)
«Оно разродилось»: последний билд Nemerle торжественно удостоился названия 1.0. В комплект входят плагин для 2008 Студии, среда на основе Шелл-Студии для неимущих, плюшки а-ля "batteries included" в ассортименте и все необходимое для жизни. Долгих лет счастья им. Забирайте.
Пока у меня гребаная сессия разгрузится, я с этой игрушкой позабавиться смогу не раньше как к середине июня :(

«Старый конь борозды не испортит. Старый конь борозды не видит». Слухи о грядущей свежей Студии. К вашим услугам тысяча и одна красивая табличка для проджект-менеджеров, умные методологии разработки ПО в комплекте, SketchFlow мертв и предан забвению, его младший брат спешит на помощь в костюмчике от ПаверПойнта (убейте меня веником).
Из позитивного пока что — все популярные юнит-тест фреймворки из коробки, и — о диво! — снова здравствуй, добрый дружище C++! Я имею против тебя много всего замечательного, но, должен признать, ребята из Редмонда делают все возможное, чтобы программирование на тебе хоть иногда текло плавно и с улыбкой, а не с ломом и такой-то матерью.
О F# ни словечка с самого PDC. Ну-ну.

Racket

Thursday, 7 April 2011 08:44
skiminok: (!int)
Оказывается, уже полгода как PLT Scheme переименовали в Racket.
Блиин, как можно было губить такой бренд? Ему 40 лет как-никак, его знают все, кто хотя бы касался SICP, а тут теперь что-то невнятное.
Тем более слово "Scheme" читается вслух как «Ским», что мне весьма импонировало :)
skiminok: (Default)
Читать тут

Мой очередной ночной труд. К сожалению, из-за того что на Хабре чертово драконовское ограничение на объем статьи, полностью осветить вопрос не получилось, пришлось пожертвовать парочкой параграфов (делить на несколько статей уж сильно не хотелось).

Но все равно, как по мне, получилось неплохо. Конечно, в первую очередь inspired by [livejournal.com profile] antilamer :)
skiminok: (Compas)
За последние несколько месяцев у меня набралось несколько планов на статьи, которых сильно не хватает хабра-аудитории. В целом они делятся на три больших класса: ФП, Computer Science и ACM-алгоритмистика.

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

  • FParsec - "утереть нос" товарищу Дмитрию mezastel Нестеруку :)

  • Списочные гомоморфизмы. Свертка. Сканирующие пробеги. Короче, основы Vector Models for Data-Parallel Computing, и немного про MapReduce с математической стороны вопроса.

  • Структура данных Rope, на основании уже существующего моего цикла про декартово дерево.

  • В рамках той же темы "Основы Computer Science: ликбез для птушников" - λ-исчисление, порядок редукций, теорема Черча-Россера, и как отсюда логически выходят потоки и ленивые вычисления. Ссылки на SICP и ПФП.

  • (?) Что-то про теорему Райса и теоретически вычислимые алгоритмы. Можно и классы сложности упомянуть.

  • Дерево отрезков.

  • (?) Дерево Фенвика.

  • Суффиксный массив, его применения. Возможно - суффиксный автомат и дерево. Уже почти год хочу рассказать, офигенная вещь ведь.


To be continued...
skiminok: (xkcd)
Простой и в то же время кошмарный пример, демонстрирующий Силу и Мощь показательной функции.

> let f0 x = (x, x);;

val f0 : 'a -> 'a * 'a

> let f1 x = f0 (f0 x);;

val f1 : 'a -> ('a * 'a) * ('a * 'a)

> let f2 x = f1 (f1 x);;

val f2 :
  'a ->
    ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
    ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))

> let f3 x = f2 (f2 x);;

val f3 :
  'a ->
    ((((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))) *
     (((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))))) *
    ((((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))) *
     (((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))))


Если вам не жаль свой fsi.exe, можете пойти еще дальше:
> let f4 x = f3 (f3 x);;

Моя консоль честно трудилась 42 секунды, выводя тип этой функции на экран. В её возвращаемом значении 65536 упоминаний 'a.
skiminok: (xkcd)
Боянистый, правда, до ужаса, но тем не менее красивый.

Взять список чисел на входе. Вернуть на выходе список списков: все перестановки заданных чисел.
Иллюстрирует:
  • List comprehensions
  • Правую свертку
  • Композицию функций
Если бы авторы F# изгнали мочу из головы и поставили, как все нормальные люди, аргумент-список в foldBack на последнее место, то иллюстрировал бы еще и частичное применение / карринг. (Правда, для этого потребуется изгнать мочу и из компилятора, а то получим радостный Value restriction, будь он неладен.)
Будучи дословно переведенным на Haskell, иллюстрирует ленивую генерацию списка. На F# для этого потребуется seq, который некрасиво пишется :-)

 let permute xs =
     let rec insert x = function 
         | [] -> [[x]]
         | y::ys -> (x::y::ys)::[for res in insert x ys -> y::res]
     List.foldBack (insert >> List.collect) xs [[]]

Работа:

> permute [1..4];;
val it : int list list =
  [[1; 2; 3; 4]; [2; 1; 3; 4]; [2; 3; 1; 4]; [2; 3; 4; 1]; [1; 3; 2; 4];
   [3; 1; 2; 4]; [3; 2; 1; 4]; [3; 2; 4; 1]; [1; 3; 4; 2]; [3; 1; 4; 2];
   [3; 4; 1; 2]; [3; 4; 2; 1]; [1; 2; 4; 3]; [2; 1; 4; 3]; [2; 4; 1; 3];
   [2; 4; 3; 1]; [1; 4; 2; 3]; [4; 1; 2; 3]; [4; 2; 1; 3]; [4; 2; 3; 1];
   [1; 4; 3; 2]; [4; 1; 3; 2]; [4; 3; 1; 2]; [4; 3; 2; 1]]

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


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

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: (Default)

open System

open System.IO

 

do

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

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

    let readLine _ = reader.ReadLine()

 

    let testCount = reader.ReadLine() |> int

    let split (s: String) = s.Split(' ') |> List.ofArray

    let gcd a b = bigint.GreatestCommonDivisor(a, b)

 

    let solve (y::_ as moments) =

        Seq.pairwise moments

        |> Seq.map (fun (x,y) -> abs(y-x))

        |> Seq.reduce gcd

        |> fun g -> (g - (y % g)) % g

 

    List.init testCount

        (readLine >> split >> List.map bigint.Parse >> List.tail >> List.sort >> List.rev)

    |> List.map solve       

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

skiminok: (xkcd)
Простенькая задача А отлично ложится на F#. Как-то так.

open System

open System.IO

 

do

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

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

    let readLine _ = reader.ReadLine()

 

    let testCount = reader.ReadLine() |> int

    let split (s: String) = s.Split(' ') |> fun arr -> int arr.[0], int arr.[1]

 

    List.init testCount (readLine >> split)

    |> List.map (fun (N, K) -> (K+1) % (1 <<< N) = 0)

    |> List.map (fun b -> if b then "ON" else "OFF")

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



А С-шку сдавал на C#, она не так красиво выглядит в итоге.

using System.Linq;

using System.IO;

 

namespace CodeJamCs

{

    class Program

    {

        static void Main(string[] args)

        {

            using (var reader = new StreamReader("C.in"))

            using (var writer = new StreamWriter("C.out"))

            {

                int testCount = int.Parse(reader.ReadLine());

                for (int test = 0; test < testCount; ++test)

                {

                    var line = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();

                    int r = line[0], k = line[1], n = line[2];

                    var size = reader.ReadLine().Split(' ').Select(long.Parse).ToArray();

                    var shift = new int[n];

                    var cost = new long[n];

 

                    for (int sh = 0; sh < n; ++sh)

                    {

                        long sum = 0;

                        int i, cnt;

                        for (i = (n - sh) % n, cnt = 0; cnt < n && sum <= k; i = (i + 1) % n, ++cnt)

                            sum += size[i];

                        i = (i + n - 1) % n;

                        if (sum > k)

                            sum -= size[i];

                        shift[sh] = (n - i) % n;

                        cost[sh] = sum;

                    }

 

                    long totalCost = 0;

                    for (int i = 0, curShift = 0; i < r; ++i, curShift = shift[curShift])

                        totalCost += cost[curShift];

 

                    writer.WriteLine("Case #{0}: {1}", test + 1, totalCost);

                }

            }

        }

    }

}

 

skiminok: (xkcd)

Повторяя прочитанный у Евгения [livejournal.com profile] antilamer Кирпичева материал про свертки, залез попутно в область, которую я пока не покрывал: префиксные суммы, сегментированные пробеги, и их связь со сверткой. И обнаружил там весьма занимательный для функциональщика алгоритм для построения выпуклой оболочки под названием Quick Hull. Короткую его реализацию с помощью сегментированных пробегов я пока оставил до лучших времен, а вот простой наивный перевод на F# определения алгоритма у Кирпичева почему бы и не сделать.

Тем более что получается это очень просто. Весь код помещается в пределах одного экрана. Вроде бы без багов :)

UPD: Поубирал все явные декларации типов в функциях алгоритма. Компилятор F# умный, сам все выводит.


type Point =

    { x: float; y: float; }

    static member (<) (a: Point, b: Point) =

        (a.x < b.x) || (a.x = b.x && a.y < b.y)

    static member (-) (a: Point, b: Point) =

        { x = a.x - b.x; y = a.y - b.y }

    static member (^^) (a: Point, b: Point) =

        a.x * b.y - b.x * a.y

    override this.ToString() =

        sprintf "(%f, %f)" this.x this.y

 

type Segment = { start: Point; finish: Point }

 

let quickHull points =

    let rec hullStep line = function

        | [] -> [line.start; line.finish]

        | points ->

            let p, q, PQ = line.start, line.finish, line.finish - line.start

 

            let distKey a = (p - a) ^^ (q - a)

            let a = List.maxBy distKey points

            let AP, AQ = (p - a), (q - a)

 

            let besidesP x = (AP ^^ PQ) * (AP ^^ (x - p)) < 0.0

            let besidesQ x = (AQ ^^ (x - q)) * (AQ ^^ PQ) > 0.0

            let pointsOfP = List.filter besidesP points

            let pointsOfQ = List.filter besidesQ points

 

            let ansP = hullStep {start = a; finish = p} pointsOfP

            let ansQ = hullStep {start = a; finish = q} pointsOfQ

            ansP @ ansQ

 

    let p, q = List.min points, List.max points

    let PQ = q - p

 

    let upper (x: Point) = PQ ^^ (x - q) > 0.0

    let lower (x: Point) = PQ ^^ (x - q) < 0.0

    let upPoints, downPoints = List.filter upper points, List.filter lower points

 

    let ansUp = hullStep {start = p; finish = q} upPoints

    let ansDown = hullStep {start = q; finish = p} downPoints

    ansUp @ ansDown |> Set.ofList |> Set.toList

 

let example = [ { x = 0.0; y = 0.0 };

                { x = 0.0; y = 1.0 };

                { x = 1.0; y = 1.0 };

                { x = 1.0; y = 0.0 };

                { x = 0.5; y = 0.8 } ]

let hull = quickHull example

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!

Вот так концепции ФП незаметно втираются в нашу повседневную жизнь. Да, девочкам-фанаточкам Сумерок — привет ;)
skiminok: (Ы)
«Впервые понятие комбинатора и основанная на нём теория были сформалированны М.И.Шейнфинкелем в работе Schonfinkel (1924) ещё до появления лямбда-исчисления. Вскоре после этого аналогичные результаты были получены Карри, независимо от Шейнфинкеля и Чёрча. Когда Карри ознакомился с работами Шейнфинкеля, он предпринял попытку с ним связаться, но к этому времени Шейнфинкель оказался в психиатрической лечебнице».


© Введение в функциональное программирование.

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, на котором оно построено, имеют разную природу, синтаксис вызова и парадигму. И потому при переходе из одного мира в другой, и обратно, приходится порою чесать себе затылок.

"Запад есть запад, Восток есть Восток, и им не сойтись никогда". ©

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