?

Log in

YCombinator в JavaScript

 Недавно стал изучать JavaScript... И пришла в голову идея написать Y-Combinator на JavaScript (на уникальность не претендую :) )...

Вот получился такой кусочек кода, где есть Y-Combinator и функция факториала, написанная в саморекурсивной форме, используя только безымянные функции:


function write(x)
{
   document.getElementById('YCombinator').innerHTML += x + '<br/>';
}

function YCombinator(f)
{
   return function (x)
   {
      return (f(YCombinator(f)))(x);
   };
}

var factor = function (fact)
{
   return function (x)
   {
      return (x<=1)?1:fact(x-1)*x;
   };
};

write(YCombinator(factor)(5));


Результатом будет 120, как и ожидалось.

Выводы:
  1. Вид самого Y-Combinatora получился довольно изящный
  2. Написание саморекурсивных безымянных функций слегка громоздко
  3. Использовать можно, но весьма на любителя
Спасибо за внимание!

Правило трёх ударов.

1 удар. Делая что-то в первый раз, Вы просто это делаете.
2 удар. Делая что-то аналогичное во второй раз, Вы морщитесь от необходимости повторения, но все-таки повторяете тоже самое.
3 удар. Делая что-то похожее в третий раз, вы начинаете рефакторинг.

© Martin Fauler
Итак, давно была мысль описать вероятностную машину Тьюринга (ВМТ). По-моему гениальнейшее теоретическое изобретение :)

Определение. ВМТ - это вид недетерминированной машины Тьюринга, в котором каждый шаг, где есть недетерменированный выбор, делается случайно.
При этом,  существует 2 способа (при желании можно создать гораздо больше способов) определения случайного шага:
  1. Мы создаем такое устройство, которое будет эмулировать подкидывание монетки, тогда, очевидно, мы сможем выбрать следующий шаг случайно.
  2. Создаем у нашей МТ (машины Тьюринга) вторую полубесконечную ленту, на которой записана в случайном порядке последовательность 0 и 1. Далее, будем использовать эту ленту, как устройство, описанное в пункте 1.
 У ВМТ следует ввести понятие вероятности ветки вычисления b:
Pr[b] = 2-k,
 где k - это число "подкидывания монетки" в ветке вычисления b.
Тогда определим вероятность того, что ВМТ М допускает слово w:
 
Pr[M допускает w] = ∑Pr[bi],
 
где bi - i-ая ветка вычисления, которая допускает слово w.
Так же очевидна следующая формула:
Pr[M отвергает w] = 1 - Pr[M допускает w].
 
Для 0≤ε<0.5 мы можем сказать, что ВМТ М распознает язык А с вероятностной ошибкой ε, если:
  1. Если w∈A, тогда Pr[M допускает w] ≥ 1 - ε, и
  2. если w∉A, тогда Pr[M отвергает w] ≥ 1 - ε.
Определение. Класс языков BPP - это такой класс языков, что распознаются вероятностными машинами Тьюринга за полиномиальное время с вероятностной ошибкой 1/3. 
На самом деле возникает вопрос, почему взято именно число 1/3. Ответ следует после следующей леммы:
Лемма. Пусть есть фиксированная константа ε находящаяся в промежутке от 0 до 0.5. Тогда для любой полиномиальной функции poly(n) ВМТ, вычислимая за полиномиальное время, M1 с ошибкой ε эквивалентна ВМТ, вычислимой за полиномиальное время, M2 с вероятностной ошибкой 2-poly(n)
Таким образом, 1/3 взята просто из критерия того, что 0<1/3<1/2. 
Недавно столкнулся с проблемой создания двунаправленных списков в F#. Решение оказалось ужасно простое...

let L = [1;2;3;4;5;6]; - Создаем основной список

Основной способ создания двунаправленного списка - это разделение основного списка на два списка (будет создана пара списков). Первый список будет хранить пройденные элементы, а второй еще не пройденные элементы. Тогда Движение по списку будет осуществленно следующим образом:

let iteratorNext j=
    let Next m=
        match m with
        |(h,[])->(h,[])
        |(h,h1::t1)->(h1::h,t1)
    Next j
;;
- Движение по списку вперед (подается в функцию пара списков)

let iteratorPrev j=
    let Prev m=
        match m with
        |([],h)->([],h)
        |(h::t,h1)->(t,h::h1)
    Prev j
;; - Движение по списку назад (подается в функцию пара списков)

Остается теперь только создать функцию получения элемента из списка. Мы просто будем брать первый элемент из второго списка в паре:

let GetElement k =
    match k with
    |(h,h1::t1) -> h1
;;
- Получение элемента списка

Ну и для примера, мы пройдем по списку 2 раза вперед, один раз назад и получим элемент из него:

let GetElement k =
match k with
|(h,h1::t1) -> h1
;;
- будет выведено число "2"


Вот вроде мы и получили двунаправленный список! :)
Нашел довольно интересный электронный журнал по функциональному программированию:fprog.ru =) Можно на досуге почитать=)

Установил Windows 7

Установил Windows 7. Работает быстрее, чем Vista.  Красивое оформление=)
Так же порадовал PowerShell. В-общем, мне пока всё нравится=)

Метки:

1 сентября

 Вот и завтра 1 сентября....
Итоги за лето: половина книги foundation of F#, и ознакомился с QT. Так больше никаких результатов особых.
По-видимому год будет тяжелый...

Грязь

 Заметка не будет очень большой. Сегодня с другом ходили пешком до метро Строгино (приблизительно 8 -10 км). На ногах грузики, каждый грузик по 1,5 кг... и идет маленький моросящий дождь....

Так вот. Во время пути встретился участок (1,5 км приблизительно)  дороги (если это можно назвать дорогой уже), где из-за дождя дорога превратилась в месиво из грязи...

В итоге я вывел несколько правил хождения по грязи:
1. Если идете по грязи, идите там, где еще растет трава.
2. Если идете по грязи, идите там, где есть камни большие или малые, без разницы.


В-общем даже если оказался в ситуации, что приходится идти по грязи, то ищите всевозможные подобия "фундамента". Ну и последнее правило, которое вывел:
3. Старайтесь выбирать чистую дорогу! (а если полез в грязь, не надевай 3 кг на ноги...)

Мораль: если влип по уши в грязь, не сдавайся! :)

День ИТ в МАИ

 Всем доброго времени суток!

17 апреля 2009 года в МАИ будет проводится день информационных
технологий!

Темы дня:

    - SilverLight 3.0
    - Windows 7
    - F#
    - Robotics Studio

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