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

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)
Этим вечером я, будучи очень начинающим функциональщиком, чисто тренировки ради решил написать на 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)

Я год назад не интересовался и не просматривал видео с конференции PDC, поэтому только сейчас наткнулся на этот превосходный доклад:





По своей привычной традиции, процитирую самые замечательные шутки и фразы из речи докладчика )

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