Встречайте новый язык программирования — Sifflet 1.0

Рекурсию надо изучать на LISPе. Вместе с макросами.

>> И спорить с такими ньюбами смысла нет. Они просто не поймут, о чём идёт спор :) Так что они или со временем станут олдфагами, всегда открытыми для чего-то нового, или уйдут со сцены :)

Перефразируя известное высказывание, в современном мире происходит много нового и интересного. Только интересное - не ново, а новое - не интересно.

>Причём здесь привычка? Со своей стороны использую рекурсию широко, но тем не менее считаю, что совать её во все дыры - полнейший идиотизм.

Именно что при том. Ты привык писать все циклами, хотя в 90% они лишь загромождают тебе код. Я тоже когда-то лишь использовал широко.

А языки ради этого городить - шизофрения.

Язык для целей обучения, успокойся.

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

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

>Рекурсию надо изучать на LISPе. Вместе с макросами.

как минимум... странное утверждение =) Нет я не против лиспа, но макросы то тут при чем? =)

>> И спорить с такими ньюбами смысла нет. Они просто не поймут, о чём идёт спор :) Так что они или со временем станут олдфагами, всегда открытыми для чего-то нового, или уйдут со сцены :)

Перефразируя известное высказывание, в современном мире происходит много нового и интересного. Только интересное - не ново, а новое - не интересно.

Эхм... да разуй глаза! Я вот не успеваю читать, столько всего.

> Дам. Тупая пузырьковая сортировка.

рекурсивно

fun bubble_h (data, i) if (data[i] > data[i+1]) swap... i-- else i++

if i < data.length - 1 bubble (data, i)

итеративно

void bubble(data) { i = 0; do{ if (data [i] > data [i+1]) { swap... i--; } else i++; }while(i < data.length - 1) }

монопенисуально

А рекурсивный факториал? ;)

>> Именно что при том. Ты привык писать все циклами, хотя в 90% они лишь загромождают тебе код. Я тоже когда-то лишь использовал широко.

Это называется итеративным подходом, а не «циклами», так как он более объемлющ, чем просто циклы. Я _не_ использую итеративный подход. Дальше что?

Циклы, как и рекурсия, в представленном здесь виде, одна из управляющих структур. Одна из. Молиться на рекурсию, всё равно что питаться одними пельменями или сажать повсеместно одну кукурузу.

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

Вот вот, я именно об этом. Кругом одни плюшки. Опять молодёжь занимается поиском серебрянных пуль.

Эхм... да разуй глаза! Я вот не успеваю читать, столько всего.

И на заборе много чего написано. Макулатуры полно, а хороших книг мало и подавляющее большинство было издано до писюкового бума. Сейчас выходят отдельные интересные исследования, на английском ессно, на русском вообще ничего толкового нет - одна коммерческая беллетристика.

Разница в том, что фолд «слева-направо» оптимальнее.

Its depend. Можно сделать чтобы не было разницы (в эффективности).

Всё таки продолжу тираду про то что «ФП и императивщина - одна фигня».

One of the enduring myths about functional programming languages is that they are somehow non-algorithmic. On the contrary, the idea of functional programming is to present algorithms in a more transparent form, uncluttered by housekeeping details.

-- Total Functional Programming, D.A.Turner

В любом случае, мы выражаем (кодируем, реализуем, прячем, программируем, etc.) вычисления в терминах вычислителя - при императивном программировании в терминах State Machine, при функциональном - в терминах Lambda Calculus. Это не декларативные выражения (мы можем нарваться на error или _|_ и в том и в другом случае). Вот когда мы говорим на языке АТД и морфизмов (sic!) (например List и fold) - это действительно декларативное описание вещей. Я утверждаю что перевод этого описания в форму SM (императивщина) или LC (функциональщина) - вещи подобные, можно делать трансляцию либо в ту, либо в другую (либо даже сначала в одну, и через неё уже в другую).

В свете этого «изучение рекурсии» это как «изучение цикла» - оно не учит «программированию», оно просветляет одну конкретную деталь конкретного вычислителя (в данном случае LC в функциональном программировании).

Вообще, строить программы в виде деревьев учат и в SICP (причём сразу, на то они и скобочки там), рекурсивные записи/процессы, как и ленивые/энергичные вычисления - тоже не обойдены вниманием :)

Короче, что лучше один раз прочитать SICP, чем написать сто «программ» для этого языка программирования :)

> Its depend.

It depends.

Можно сделать чтобы не было разницы (в эффективности).

Да неужели? А можете продемонстрировать? И что подразумеваете под эффективностью?

>Циклы, как и рекурсия, в представленном здесь виде, одна из управляющих структур.

рекурсия не является управляющей структурой.

Да неужели? А можете продемонстрировать? И что подразумеваете под эффективностью?

Речь идёт о сложности как я понял, и, возможно, о более тонком различии (коэффициент в выражении время = коэф. * вход, который в оценках сложности не учитывается).

И foldl и foldr могут быть реализованы так, что алгоритм будет иметь оценку O(n). Другое дело, что для foldl это O(n = k), а для foldr O(n = 2*k). Но этот недостаток тоже может быть устранён.

Про то какие ограничения вносит ленивость - ничего не знаю. Если что - можем развить эту тему в коде.

Its depend.

Ага, s уехала из одного слова в другое :)

В любом случае, мы выражаем (кодируем, реализуем, прячем, программируем, etc.) вычисления в терминах вычислителя

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

(мы можем нарваться на error или _|_ и в том и в другом случае)

не совсем понятно, что значит нарваться на error. Суть функциональщины - x=3+5 Где тут место для ошибок?

Я утверждаю что перевод этого описания в форму SM (императивщина) или LC (функциональщина) - вещи подобные, можно делать трансляцию либо в ту, либо в другую (либо даже сначала в одну, и через неё уже в другую).

Проблема состоит в преобразованиях самого алгоритма, а не его реализации в той или иной нотации. Например,

x = 0 for (i = 1, i<100, i++) print x

тоже самое, что

for (i = 1, i<100, i++) print 0

?

В императивном ЯП, нет возможности понять, да или нет. А в функциональном есть.

В свете этого «изучение рекурсии» это как «изучение цикла» - оно не учит «программированию»,

циклы - основа императивного программирования. рекурсия - основа функционального программирования. изучение рекурсии позволяет понять, как программируются процессы в функциональных ЯП.

>Это называется итеративным подходом, а не «циклами», так как он более объемлющ, чем просто циклы. Я _не_ использую итеративный подход. Дальше что?

Бред... просто бред. Тем не менее спрошу, что же ты используешь? =)

Циклы, как и рекурсия, в представленном здесь виде, одна из управляющих структур. Одна из.

Управляющая структура? втф?

Молиться на рекурсию, всё равно что питаться одними пельменями или сажать повсеместно одну кукурузу.

А при чем тут молиться? Тем более, я же писал, что рекурсия+ФВП. Про аналогию твою напишу отдельным постом.

Вот вот, я именно об этом. Кругом одни плюшки. Опять молодёжь занимается поиском серебрянных пуль.

Ха! Все развитие человечества состояло в поиске новых решений, подходов для часто уже решенных проблем. И кто говорит о серебрянных рулях? Следуя твоим подходом к жизни, мы бы до сих пор писали исключительно на ассемблере.

И на заборе много чего написано. Макулатуры полно, а хороших книг мало и подавляющее большинство было издано до писюкового бума. Сейчас выходят отдельные интересные исследования, на английском ессно, на русском вообще ничего толкового нет - одна коммерческая беллетристика.

Как с тобой все запущено. Книги выходят как правило только о проверенных, устоявшихся вещах. Это как в математике. По мат.анализу много хороших книг, но по проблемам сегодняшнего дня их естественно по сути и нет. Не от куда взяться. Хочешь читать о новом и интересном, читай статьи. Статьи!

>Молиться на рекурсию, всё равно что питаться одними пельменями или сажать повсеместно одну кукурузу.

Аналогии - говно. Твоя аналогия - полное говно. Ты ведь не кашу варишь, а программы пишешь. Суну ка и я сюда свою аналогию =). Это все равно что при проектировании устройства, совать туда в перемешку соединения а метрических и дюймовых резьбах. Что-бы скучно не было.

Суть функциональщины - x=3+5 Где тут место для ошибок?

Т.е. суть функциональщины в таких вот математических выражениях задачи? При этом они не подчиняются математическим законам которым (интуитивно) должны подчиняться:

loop :: Int -> Int
loop n = 1 + loop n

-- по-simple-man-овски:
(loop 0) = 1 + (loop 0)
(loop 0) - (loop 0) = 1
0 = 1

Это потому что тип Int не математический тип (множество) а тип теории типов, содержащий помимо конечного набора целых ещё и _|_(Int).

Ещё:

hd :: [a] -> a
hd (x:xs) = x

hd []
--> _|_

А это потому что List не является замкнутым относительно конструкторов множеством - опять не математический тип и функций - частичные, а не математические. Можно разве что исправить спецификацией:

hd :: [a] -> a
hd [] = []
hd (x:xs) = x

Более подходящий пример: упоминалось выше про то что foldl и foldr отличаются по эффективности (один итеративен, другой - нет). Это не ошибка, но следствие той же неполноты типа List, его расширение (замыкание) позволяет ввести foldl и foldr итеративные и ничем не отличающиеся (т.е. нужен только один общий fold).

Вот такие ошибки и казусы есть в ФП, «ошибки» (такое обобщённое понятие) свойственны любому вычислителю. Вот я и говорю - императивный он, функциональный - одна фигня :)

> Речь идёт о сложности как я понял, и, возможно, о более тонком различии (коэффициент в выражении время = коэф. * вход, который в оценках сложности не учитывается).

И foldl и foldr могут быть реализованы так, что алгоритм будет иметь оценку O(n). Другое дело, что для foldl это O(n = k), а для foldr O(n = 2*k). Но этот недостаток тоже может быть устранён.

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

Про то какие ограничения вносит ленивость - ничего не знаю. Если что - можем развить эту тему в коде.

Ленивость позволяет в одном из случаев вычислять fold шаг за шагом, не держа в памяти кучу хлама. Причем приличными компиляторами это преобразуется в довольно компактных native code. А в другом случае будет построен список невычисленных выражений (см выше), пропорциональный длине входных данных. И лишь потом он будет сворачиваться. Кстати, в случае бесконечного входного потока получим переполнение памяти.

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

>Т.е. суть функциональщины в таких вот математических выражениях задачи? При этом они не подчиняются математическим законам которым (интуитивно) должны подчиняться:

ха, так f(int) не означает int. Фактически loop (n) никогда не вычислиться, поэтому

loop = 1 + loop также верно, как

неопределенность = 1 + неопределенность

А для этого уже придуманы комплексные числа.

Можно разве что исправить спецификацией:

а факториал «исправляют» спецификацией F(0)=1. А деление на ноль - нельзя (а должно бы бесконечность) и т.п.

Вот такие ошибки и казусы есть в ФП, «ошибки» (такое обобщённое понятие) свойственны любому вычислителю

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

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

О, тонкий троллиг...

Вообще, foldl забанен в хаскеле. Зараза, создает слишком много санков. Тут еще (++) вносит свою лепту, копируя первые элементы помногу раз. Неэквивалентны по сложности свертки ни разу.

Вообще, foldl забанен в хаскеле. Зараза, создает слишком много санков. Тут еще (++) вносит свою лепту, копируя первые элементы помногу раз. Неэквивалентны по сложности свертки ни разу.

Непонятно. Давайте сначала рассмотрим как оно в GHC. Три вопроса:

a) Какова оценка по времени?

b) По памяти?

с) Есть ли оверхед санков?

Три функции:

1) foldl, это который TCO оптимизируется, т.е. преобразуется в цикл. Но он non-strict:

-- We write foldl as a non-recursive thing, so that it
-- can be inlined, and then (often) strictness-analysed,
-- and hence the classic space leak on foldl (+) 0 xs

foldl        :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

a) O(n)

b) оверхед санков

c) что с памятью?

2) foldl' тоже самое, но strict

-- | A strict version of 'foldl'.
foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f z0 xs0 = lgo z0 xs0
    where lgo z []     = z
          lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs

a) O(n)

b) нет

c) ?

3) foldr не пишется в TCO форме. Не рекурсивный процесс. Поэтому для него нет strict версии.

foldr            :: (a -> b -> b) -> b -> [a] -> b
-- foldr _ z []     =  z
-- foldr f z (x:xs) =  f x (foldr f z xs)
{-# INLINE [0] foldr #-}
-- Inline only in the final stage, after the foldr/cons rule has had a chance
foldr k z xs = go xs
             where
               go []     = z
               go (y:ys) = y `k` go ys

a) O(n)? Вроде как нет, разве что какая-то хитрющая оптимизация.

b) ?

c) ?

Ц,

3) foldr не пишется в TCO форме. Не рекурсивный процесс.

рекурсивный процесс, конечно.

> 3) foldr не пишется в TCO форме. Не рекурсивный процесс. Поэтому для него нет strict версии.

Да неужели?

Data.Foldable   foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b

Да неужели?

Ну, это хорошо :) Я не обнаружил её в Data.Base/Data.List.

Так или иначе, при реализации на линейных списках свёртки не эквивалентны друг другу. Как я говорил - это связано с тем что тип List не является алгебраически-замкнутым, и функции на нём будут частичными, а не математическими.

Чтобы разрешить эту проблему нужно поступить примерно в духе Total FP, т.е. ввести алгебраическое расширение List на котором foldr и foldr не будут отличаться друг от друга.

Таким расширением является двусвязный список-кольцо. Над таким АТД существуют две алгебры: одна «левая», другая «правая» - соответствующими катаморфизмами и будут foldl и foldr, полностью симметричные.

К сожалению, в Haskell нет возможности работать с настоящими циклическими структурами, их можно только симулировать при помощи АТД:

module Data.Ring where
import Data.List

-- Focus ADT

data Focus = Light | Dark deriving (Eq, Ord, Show)

-- Ring ADT

data Ring a = Ring (Ring a) (a, Focus) (Ring a) deriving (Eq, Ord)

type RingRAlgebra a r = (r -> a -> r, r)
type RingLAlgebra a r = (a -> r -> r, r)

-- cata

ringataR :: RingRAlgebra a r -> Ring a -> r
ringataR (f, i) ring = go i ring
                     where go i (Ring l (x, Dark) r)  = go (f i x) r
                           go i (Ring l (x, Light) r) = i

ringataL :: RingLAlgebra a r -> Ring a -> r
ringataL (f, i) ring = go i ring
                     where go i (Ring l (x, Dark) r)  = go (f x i) l
                           go i (Ring l (x, Light) r) = i

-- simple accessors

element :: Ring a -> a
element (Ring _ (x, _) _) = x

left :: Ring a -> Ring a
left (Ring l _ _) = l

rigth :: Ring a -> Ring a
rigth (Ring _ _ r) = r

focus :: Ring a -> Focus
focus (Ring _ (_, f) _) = f

-- []-lists -> rings
-- I don't like it, functors woude be greate there.

ring :: [a] -> Ring a
ring [] = error "Must have at least one element."
ring xs = Ring (ring $ rot (-1) xs) ((head xs), Dark) (ring $ rot 1 xs)
        where rot :: Integer -> [a] -> [a]
              rot n xs | n < 0  = rot (n+1) ((last xs):(init xs))
                       | n == 0 = xs
                       | n > 0  = rot (n-1) (tail xs ++ [head xs])

-- rings -> []-lists
-- And there.

takeL :: Integer -> Ring a -> [a]
takeL 0     _               = []
takeL (n+1) (Ring _ (x, _) r) = x : (takeL n r)

takeR :: Show a => Integer -> Ring a -> [a]
takeR 0     _               = []
takeR (n+1) (Ring l (x, _) _) = x : (takeR n l)

-- Other functions

-- O(1)!

ring_Head   = element
ring_Second = element . rigth
ring_Last   = element . left

{-
  Examples:

  takeL 3 (ring [1,2,3,4,5])
  => [1,2,3]

  takeL 20 (ring [1,2,3,4,5])
  => [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]

  takeR 7 (ring [1,2,3,4,5])
  => [1,5,4,3,2,1,5]

  ring_Last (ring [1,2,3,4,5])
  => 5
-}

-- O(N)!

-- Note: is all isomorphism - Ring-Rigth-Algebra <-> Ring-Left-Algebra
--       so we can use ringataR or ringataL - its equavalence.

-- WTF?

-- Get left algebra:
-- ring_LLength :: RingLAlgebra a Integer
-- ring_LLength = ((\ _ i -> 1 + i), 0)

-- Get rigth algebra:
-- ring_RLength :: RingRAlgebra a Integer
-- ring_RLength = ((\ i _ -> 1 + i), 0)

test_1 = ringataR ((\ i _ -> 1 + i), 0) (ring [1,2,3,4,5])
-- => infinity loop, because ring is unlighted.

test_2 = ringataR ((\ i _ -> 1 + i), 0)
           (Ring (left dark_ring) ((element dark_ring), Light) (rigth dark_ring))
           where dark_ring = (ring [1,2,3,4,5])
-- => 0, because we lighted exactly first element.

-- We can ligthing last element while build the list, and mutable (oh, ok, reconstruct) it.
-- But anywere:

-- Problem: seems like real circular ADT in Haskell is impossible:
--          if we lighting element on `left' from `fisrt' we NOT lighting *real* `last' element.
--          So, there is, in haskell, no memory-compacted circulat ATD objects (is it?),
--          and if we run infinite loop (with `ringata') on finite (theoreticly) ring
--          its produce infinite memory usation. So, its crap!

Но примерно так это можно реализовать на языке в котором есть возможность работы с циклическими структурами (может в Haskell и есть, я не знаю).

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

присваивание, это goto второго порядка, опасная и ненужная операция.

Посему рулит Common Lisp.

На практике CL не позволяет использовать в полной мере ни ФП, ни алгебраическое программирование. Императивное, объектно-ориентированное, аспектно-ориентированное, и метапрограммирование - это да, пожалуйста.

(«можно прикрутить» - это тоже да, но пока никто не прикрутил)

Кстати, как насчёт настоящих циклических РТД в Haskell? Чтобы было компактно по памяти.

> присваивание, это goto второго порядка, опасная и ненужная операция.

Плюсую, весьма справедливое утверждение.

> присваивание, это goto второго порядка, опасная и ненужная операция.

В общем так оно и есть, если не знать меры. В C++ иногда goto таки не хватает. Хорошо, что в CL есть return-from, который покрывает все возможные случаи нехватки goto. Правда и в ФЯ можно свести на нет необходимость в присваиваниях использованием let и внутренних определений функций или упаковкой длинных списков параметров в структуры. Просто зачем эмулировать то, что можно не запрещать? Правда при использовании многопоточности от простых присваиваний лучше таки воздержатся и дать возможность компилятору самому распаралелить чистый функциональный код.

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

сам спросил, сам ответил. Осталось только добавить, что сегодня во всех компах минимум два ядра, а любой гуй предполагает многопоточность. То есть параллелить код нужно чуть чаще, чем всегда.