[haksell] итерационные вычисления

псевдокод опасный

>founded

By whom? And when?

Явные итерации в хаскеле должны быть уголовно наказуемым деянием.

2) Насколько я помню, в ФП итерации нельзя, ибо side effects. Нужно преобразовать for в рекурсию как-то так:

псевдокод (тривиально же ... хелловорлд ибо (точнее факториал))

iterate(f, n) :
  if(n < 10^7) then
    if f n == x then 
      printf "n found  (n)!"
    else
      printf "testing n failed";
    iterate(f, n+1);
  end

> Дабы избавиться от излишней ленивости, используем рекурсию.

Влом вникать, где х определен и зачем здесь избавляться от ленивости?

Нельзя так: find f = snd . head . filter fst . map (\x -> (f x, x))

find (==42) [1..] — выведет, театральная пауза... 42

Во-первых,

find ((a==).f)  [1..10^7]

Во-вторых,

Совершенно не ясно, на каком аргументе в данный момент производится перебор.

Тебе от этого легче будет?

Ой, здесь не оригинальная f, а f' n = f n == f x (где x уже известно).

> 1) Переборную функцию, вычисляющую значение f n сразу, если оно нас не устраивает, переходящую к следующему кандидату?
Можно эту же фразу, но по-русски, а то смысл ускользает от меня?

Дабы избавиться от излишней ленивости, используем рекурсию.

Чего?

Переборную функцию, вычисляющую значение f n сразу, если оно нас не устраивает, переходящую к следующему кандидату?

А ты не это выше написал?

Некий аналог итерационного перебора

Который отличается от предыдущего только тем, что выводит сообщения?

findX :: Integer -> IO Integer
findX n = 
    if f n == x then putStrLn ("solution: " ++ show n) >> return n
    else putStrLn (show n ++ " failed") >> findX (n+1)

>if f n == x then n

else findX (n+1)

Сделайте развидеть

Почини мне!

Сейчас опять набегут тупые анонимусы и будут безапелляционно утверждать, что хацкель — говно, не приводя при этом никаких аргументов.

Ответь на два вопроса сначала:

Дабы избавиться от излишней ленивости, используем рекурсию.

Что ты имел ввиду? И что ты читал по хаскеллю?

Шестая глава rwh.

Когда встаёт задача поиска аргумента, при котором функция принимает определённое значение, первое, что приходит в голову, - фильтр с мапом. Насколько я понимаю, получается лист с множеством f x, где f раскрываются в огромные портянки (так уж реализована f).

Мне кажется, что считать все такие выражения сразу и держать их памяти - не самая лучшая идея. Хотелось бы считать их по-отдельности.

Что-то подобное я подразумеваю под «избавлением от ленивости».

Как раз именно ленивость помогает не держать весь список знкчений f в памяти, пока find'ом ищется нужное тебе значение. Так что делай в лоб find p (map f l) и все будет хорошо.

Ну, это в случае, конечно, если список ленивый. Например, если ты его генерируешь чем-нибудь. Допустим енамом — [1..100000].

for = flip mapM_

main =
  for [1 .. 10^7] $ \n ->
    if f n == x
    then printf "For n = %i, f(n) = x.\n" (n :: Int)
    else printf "There is no such n in [1 .. 10^7] for which f(n) = x.\n"

printf из модуля Text.Printf это сильно перегруженная функция которая умеет переменное количество аргументов, интерполяцию в стиле сишной printf, и может возвращать как строки, так и действия в IO. for из псевдокода это просто mapM_ из Control.Monad с переставленными аргументами (вообще, мне всегда удобнее, чтобы у функций вроде fold*, map* принимаемая функция была последним аргументом). Ну и сигнатуры к for и main я не написал (обычно полагается писать), а тип (:: Int) для printf пришлось подсказать (обратно, обычно этого делать не нужно - выводится из типов top-level функций).

может возвращать как строки, так и действия в IO

поэтому можно даже вот так:

for  = flip map
forM = flip mapM_

test1 :: [String]
test1 =
  for [1 .. 10] $ \n ->
    if id n == n
    then printf "For n = %i, f(n) = x.\n" (n :: Int)
    else printf "There is no such n in [1 .. 10] for which f(n) = x.\n"

test2 :: IO ()
test2 =
  forM [1 .. 10] $ \n ->
    if id n == n
    then printf "For n = %i, f(n) = x.\n" (n :: Int)
    else printf "There is no such n in [1 .. 10] for which f(n) = x.\n"

при этом:

test2 === mapM_ putStr test1

for из псевдокода это просто mapM_

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

{-# LANGUAGE FlexibleInstances #-}

-- -----------------------------------------------------------------------------
-- * Pseudo-imperative loops.

data LoopControl e r
  = Stop Bool r
  | Loop Bool ([e] -> [e]) r

loop :: [e] -> r -> (e -> [e] -> r -> LoopControl e r) -> r
loop xs_ z_ f = go xs_ z_
  where
    go []     z = z
    go (x:xs) z =
      let z' = f x xs z
      in z' `seq` case z' of
        Stop False _   -> z
        Stop True  r   -> r
        Loop False g _ -> go (g xs) z
        Loop True  g r -> go (g xs) r

loop' :: [e] -> (e -> [e] -> e -> LoopControl e e) -> e
loop' []     _ = error "loop' is partial function."
loop' (x:xs) f = loop xs x f

class Stop t where
  stop :: t

instance Stop (LoopControl e r) where
  stop = Stop False undefined

instance Stop (r -> LoopControl e r) where
  stop = Stop True

class Next t where
  next :: t

instance Next (LoopControl e r) where
  next = Loop False id undefined

instance Next (r -> LoopControl e r) where
  next = Loop True id

class With t where
  with :: t

instance With (([e] -> [e]) -> LoopControl e r) where
  with f = Loop False f undefined

instance With (([e] -> [e]) -> r -> LoopControl e r) where
  with = Loop True

пример (обязательно с BangPatterns):

{-# LANGUAGE BangPatterns #-}

-- -----------------------------------------------------------------------------
-- * Test.

test :: Integer
test = loop ([1 .. 20000000] :: [Integer]) 0 $
  \ !x _ _ ->
    if x * x * x == 7999998800000059999999
    then stop x
    else next

main :: IO ()
main = putStrLn $ show test

И loopM можно такой же написать. Тогда будет нормально - линейно по памяти и по времени.

В императивном CL есть iterate и loop для итераций:

(time
  (flet ((f (x) (* x x x)))
    (let ((x 7999998800000059999999))
      (iter
        (for e from 1 to 20000000)
        (when (= (f e) x)
          (return e))))))
19999999

; Evaluation took:
;   1.916 seconds of real time
;   1.920120 seconds of total run time (1.872117 user, 0.048003 system)
;   [ Run times consist of 0.140 seconds GC time, and 1.781 seconds non-GC time. ]
;   100.21% CPU
;   4,013,980,981 processor cycles
;   639,427,736 bytes consed

такой код тоже работает за линейное время и память (побыстрее, чем хаскельный вариант).

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

Ну, то есть, оно будет возвращать отложенные вычисления, и для них можно сделать потом ((find ((== x) . f) ...), как выше писали, т.е. это будет ленивый конвейер. Но если нужны именно строгие свёртки на финитных списках с использованием строгих лямбд (с BangPatterns в смысле) - тогда нужен такой loop.

> Перебор большой, от 1 до 10^7.

Лол, так вот как хаскелисты находят численное решение уравнений!
Мой совет: попробуй нормальный язык. Если есть видеокарта - сможешь вычислять миллионы значений своей функции параллельно, на CUDA.\

И да, может, стоит покурить матметоды?

Они как раз считаются не сразу, в этом и суть ленивости. RWH советую бросить, лучше gentle introduction into haskell 98, или learn yourself a haskell for greater good.

Читай учебник по алгебре, SICP, потом численные методы.

Извините за грубость, но нах*р тут cuda, когда это можно быстро решить даже на калькуляторе, 80-х годов, пусть и программируемом... 10^7))) насмешили... Включите голову. А за перебор всех вариантов неуд ТС. Нужно сразу отбрасывать заведомо плохие решения максимально быстро приближаясь к результату. Жизнь очень короткая штука, чтобы расходовать так время, пускай даже машинное.

P.S.

Матчасть, которую я осилил очень давно... если не ошибаюсь классе в 4-ом или 5-ом. Брутальный перебор это самоубийство для данного алгоритма. Даю наводку f(x)-y=0 можно очень быстро определить методом «хорд-секущих» (даже тратя время на выход из локального минимума). Следующий по порядку корень данного уравнения, ежели не ошибаюсь (пишу по памяти) ищется также просто (f(x)-y)/x1=0, следующий (f(x)-y)/x1/x2=0 и т.д. Для более детального описания ищите численные алгоритмы - вариантов настолько много, что можно составить оптимальный алгоритм почти для всего. Но во многих случаях можно настолько упростить алгоритм, что его можно будет вычислилять даже не счетах, а в уме...

P.P.S. И да, для меня нет лучшего языка, чем чистый машинный код.... Да я пишу иногда программы числами.... Исключение могу сделать только для C, Forth и Prolog. И то только в нормальных реализациях. Мнение высказал личное, на правах подсказки решения Вашей задачи. К хаскелю не имею никакого отношения.

Молодец. Мой счетчик пи^Wпозерства и самоуверенности чуть не зашкалил. А теперь залезь обратно в ту дыру, откуда выполз. Пиши там дальше свои программы на машинных кодах.

> Даю наводку f(x)-y=0 можно очень быстро определить методом «хорд-секущих».

а). только в случае удачной функции.

б). функция может быть определена только на целых числах

что правда не отменяет возможности отбрасывания заведомо неверных вариантов.

Аргументируйте, уважаемый тролль.

P.S.

Не стоит отсылать туда, где это считается нормальной средой обитания. Могут не понять. Или, как Вы поговариваете, пора «Вас записать в особый список тех, к кому надо относиться снисходительно»;))

Не стоит учебный метод применять. Нужно его чуть доработать, чтобы выползать из локальных минимумов. По факту получалось достаточно быстро. И не соглашусь, что функция будет определена только в целых числах. Может быть Вы имели ввиду комплексные числа?

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

Если писать быстро, то будет что-то вроде:

[code] import Data.Enumerator as E import Data.Enumerator.List as EL

iter :: Monad m => (Int -> Bool) -> Iteratee Int m (Maybe Int) iter act = do mx <- EL.head case mx of Nothing -> return Nothing Just x | act x -> return $ Just x | otherwise -> {-anydebugcode (maybe MonadIO) -} iter act [/code]

хотя можно и без использования Data.Enumerator.List

> И не соглашусь, что функция будет определена только в целых числах.

ты знаешь функцию использующуюся ТС? Если нет, то она _может_ быть определена только на целых числах, а рассмотрение части таких функций на R может приводить к неадекватным ситуациям

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

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

или если без Enumerator.List

iter2 :: Monad m => (Int -> Bool) -> Iteratee Int m (Maybe Int)
iter2 act = continue go
  where 
      go EOF = yield Nothing EOF
      go (Chunks xs) = let r = Prelude.filter (act) xs
                      in case r of 
                          [] -> {- anydebugcode -} continue go
                          (x:xs) -> return (Just x) 

хотя я дурень, у тебя же в посте и была реализация итерати

>В императивном CL есть iterate и loop для итераций

Да... В чем я завидую CL, так это в его шаблонах для машинного кода по типу операторов в императивных языках. Жалко, что хаскелю нельзя давать полезных советов типа «Вы, батенька, мне вот этот терм в цикл разверните, пожалуйста, и переменные, пока вы там в цикле крутитесь мне не боксите». Еще больше жалко, что нельзя без анализа дампов посмотреть в какой же машинный код развернется тот или иной терм. Даже, по моему, С- представление посмотреть нельзя. :`(

итерати

Ух ты ж ё. Но это ещё раскурить нужно :)

Жалко, что хаскелю нельзя давать полезных советов типа «Вы, батенька, мне вот этот терм в цикл разверните, пожалуйста, и переменные, пока вы там в цикле крутитесь мне не боксите».

Хмм. Какие с этим проблемы в плане реализации? Сделали бы какие-нибудь низкоуровневые монады :)

Никаких, давно сделали. И переменные можно передавать в анбокснутых туплах, и ST-монаду можно нацепить, чтобы изобразить изменяемые данные.

> Аргументируйте, уважаемый тролль.

Тащемта он все правильно сказал. Твой выпад был чертовски безграмотным и самодовольным.

Ну да. Компиляторы CL обычно пляшут от машины, наворачивая на неё всяких фишек пока не получится динамическая VM (CL вообще больше VM, чем просто язык) в которой возможно реализовать стандарт CL (и любого другого подобного языка). В итоге можно мысленно представить (да и посмотреть) чем являются любые данные/код на уровне памяти/инструкций, всё что семантически можно на уровне машины (присваивание, например) можно и в VM. Как в SBCL - все примитивные объекты представляются просто как сишные структуры, произвольные lispobj-екты как тегированные указатели, дальше некоторый набор виртуальных операторов (VOPs, это инструкции, т.е. элементы секвенций) которые умеют работать с примитивными объектами превращаются в инструкции данной архитектуры шаблонным образом, flow graph (недо-SSA) которым эти VOPы генерируются строится примитивными специальными формами (все вещи вроде let, lambda, if), а остальные трансформации и (стандартные) макросы - тоже, считай, шаблоны.

А вот хаскель начинается с абстрактного исчисления, которое имеет мало общего с машиной (ни тебе плоской памяти, ни указателей, ни присваивания), но которое нужно как-то свести к машинному представлению, при этом используются весьма нетривиальные промежуточные представления (вроде STG). Смысла вникать в ассемблер которым плюётся GHC тут мало.

У меня есть предположение, что хорошо бы было иметь некую метатеорию, то есть промежуточный формальный язык для core, которая, во-первых, была более элементарна чем LC и в которой выражались метатеории вроде SystemF или LF, во-вторых, легко компилировалась в натив т.е. была близка и к машине, и, в-третьих, позволяла проводить на себе разные мощные оптимизации, вроде уничтожения любой линейной рекурсии (GHC, вроде, не умеет?) или линеаризации (т.е. чтобы где-то выводить регионы и обходиться без GC). Ну и нужно более чётко отдавать отчёт о том что такое IO, плоская память и т.п. вещи (в смысле, в самом языке, на уровне типов).

MSIL не то?

MSIL не то?

Совсем не то. Это ассемблер, программы там - линейные последовательности инструкций, может сгодится как кросплатформенный байткод с сохранением информации об ООП которое было до компиляции, но никаких мощных оптимизаций на этом не провести (например, как убрать линейную рекурсию на байткоде?). Хорошие оптимизации обычно проводят на более сложных представлениях - деревьях (многочисленные source-to-source в CL), графах (SSA, lazy graph reduction в хаскеле).

Тест рекапчи. Не получается постить из-под анонимуса.

>А вот хаскель начинается с абстрактного исчисления, которое имеет мало общего с машиной

Но ведь любой терм имеет конечное количество машинных представлений. Если он завершается, конечно. Требуется только выбрать более целесообразное... Это не принимая во внимание IO, конечно.

была более элементарна чем LC

Что может быть элементарнее лямбда-исчисления? Чем же плохи Core и STG? System FΩ все-таки, и достаточно простой.

Кстати, я совсем забыл, что в последних GHC появились плагины компилятора типа Core -> Core. Но смысла в них для простых смертных... Т.е. хорошо, конечно, можно разрабатывать оптимизаторы-анализаторы независимо от основного дерева GHC и на хаскеле. Но для прикладников...

Мне лично кажется, что GHCшники слегка переборщили с количеством стадий. Все таки Haskell -> Core -> STG -> C-- -> LLVM -> машинный код кажется немного длинным. И даже из Core проблематично влиять на результат :(

Что может быть элементарнее лямбда-исчисления?

Например, стрелки. Единственный вариант, который я пока вижу. Нужно просто-типизированное LC это будет одна конструкция из стрелок/2-стрелок, нужно LC с зависимыми типами - другая, с субструктурными (линейными, в частности) - ещё третья. Т.е. фиксированное подмножество теории категорий само по себе довольно бедная метатеория, просто язык, в котором можно выразить все эти вещи. Мартин-Лёф предлагал формулировать разные теории типов в рамках метатеории LF, вот также это можно делать в рамках метатеории ТК.

Ну, например, берём декартово-замкнутую категорию Set, она же классический топос, т.е. категория всех малых множеств и тотальных функций, в agda она так и называется - «Set». Берём категорию всех малых категорий и функторов Cat (Set1 в agda) и утверждаем:

• Любой тип который может использоваться (ADTs, GADTs, Inductive families) это объект Set (объект топоса, в общем случае), т.е., как следствие, множество - множество всех термов данного типа.
• Любой параметрически-полиморфный тип это эндофунктор на Set, т.е. специального вида стрелка в Cat. (Непараметрический тип, который объект в Set, это вырожденный случай функтора из терминальной категории (как-то так)).
• Любой конструктор типа данных который может быть это стрелка в Set (стрелка в топосе, вообще).
• Любая функция которая может быть это тоже стрелка в Set, но отдельным классом (чтобы не путать стрелки-конструкторы и стрелки-функции). Как следствие, «функция» - тотальная функция между множествами.
• Любая композиция стрелок с учётом декартовых произведений и экспоненциалов это любой правильно составленный терм в данной системе (тут типизация из коробки).
• Любое определение конкретной редукции это 2-стрелка (струнная диаграмма).
• Любой конкретный ход редукций (вычислений) это композиции 2-стрелок (струнных диаграмм). + Правила построения редукций из коробки.

Например:

-- Тут рисуем коммутативную диаграмму:
ℕ : Set
0 : 1 → ℕ
s : ℕ → ℕ

-- Продолжаем коммутативную диаграмму:
+ : ℕ → (ℕ → ℕ)

-- Рисуем две струнных диаграммы, которые можно сочетать:
e₁(+) : + ∘ a ∘ 0 ⇒ a
e₂(+) : + ∘ a ∘ (s ∘ b) ⇒ s ∘ (+ ∘ a ∘ b)

и это просто ТК (можно представить формальный синтаксис такого языка), безотносительно какого-либо ЯП, но понятно из каких ADT и функции это получилось.

Тут ещё интересно, что можно легко добавлять конструкторы и правила редукций (как если бы в хаскеле можно было дописывать ADT и pattern matching cases по разным модулям).

Сами по себе 2-стрелки это непосредственно струнные диаграммы, т.е., рисуя коммутативные диаграммы, получим схемы типов, рисуя струнные - flow chart.

• Любая конкретная оптимизация это 3-стрелка. Правила построения оптимизаций тоже из коробки.

Например, если есть линейная рекурсия:

f x = z
f y = g (f (h y))

(f не появляется в g и h), т.е.:

-- любая стрелка вида:
f : x + y → r

-- с 2-стрелками вида:
e₁(f) : f ∘ x ⇒ z
e₂(f) : f ∘ y ⇒ g ∘ f ∘ h ∘ y

то она убирается такой 3-стрелкой:

-- Рисуем диаграмму между струнными:
o(f, f′) : e(f) ≡> e(f′ ∘ z)

-- TCO форма:
e₁(f′) : f′ ∘ a ∘ x ⇒ a
e₂(f′) : f′ ∘ a ∘ y ⇒ f′ ∘ (g ∘ a) ∘ (h ∘ y)

и остаётся только TCO.

Процесс унификации по 3-стрелкам это процесс оптимизаций, а процесс унификации по 2-стрелкам - интерпретации или компиляции (тогда нужен target). Как компилировать в target - конструкторы, например, достаточно точно отражаются в си-подобные структуры и объединения в памяти, можно даже в случае (s : ℕ → ℕ) или (_:_ : a → [a] → [a]) или вообще (con : [no `t' appears] → t → t) пытаться делать не связные списки, а аллоцируемые/реаллоцируемые массивы. Про компиляцию редукций ничего не скажу - только, наверно, тут, в первую очередь, нужен критерий линейности представляемого терма и/или его линеаризация.

Про компиляцию редукций ничего не скажу - только, наверно, тут, в первую очередь, нужен критерий линейности представляемого терма и/или его линеаризация.

А, ну ещё в данной конкретной струнной диаграмме каррированные экспоненциалы заменяются декартовыми произведениями, т.е. полный uncurring в любом случае производится.

Все таки Haskell -> Core -> STG -> C-- -> LLVM -> машинный код кажется немного длинным.

Вот в формальной «From System F to TAL» сначала делается несколько преобразований на λ (CPS, closures, hoisting, allocation) и потом сразу получается TAL. Только они на ML пишут :(

«Тащемта» не тянет на аргумент. Поясните в чем заключается «безграмотность»?

P.S. Вопрос ТС состоял в нахождении аргумента функции, причем он хотел выполнять это быстро. Разве нет?

Начиная с того, что у ТС'а функция над множеством целых чисел. Про множество действительных даже и речи не шло. Ты же предлагаешь использовать методы для поиска нулей функций действительных аргументов, причем дифференцируемых. Это совсем другой класс функций.

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

Грустно, в общем.

P.S. Постскриптум — вообще фейспалм.

Бросить до времён просветления или насовсем?

До просветления. Там совсем практические вещи, в плане IO и прочего. Советую после прочтение книжек решить пару десятков задачек с project euler, ну и вообще разобраться с системой типов, монадами, etc. Потом браться за реальные вещи.