Очередь и обработка

добавлять элементы в итерируемую коллекцию

в функциональных ЯП

You are doing it wrong.

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

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

def func(seq):
  if empty(seq):
    return []

  e, rest = seq.split()  # e это первый элемент, rest -- всё остальное
  if test(e):
    return seq + func(rest+e)
  else:
    return seq + func(rest)

в F# нельзя добавлять элементы в итерируемую коллекцию.

Этого и не в ФП языках лучше никогда не делать. Т.к. может итератор испортится. Делать надо через filter f seq который потом к seq в конец добавляешь (как это на F# написать мне лень вспоминать, слишком давно не юзал его).

P.S. Для лучшего понимания вопроса посоветую изучить как работает IEnumerable в .Net.

слово «добавлять» не нравится?

Что такое addInRest? Google на этот запрос, если включить Verbatim, находит только одну ссылку, ведущую сюда.

да я понимаю, я имею в виду саму идею итераций на не полностью сформированных коллекциях. Типа бесконечных коллекций.

addInRest = добавить в конец

Мутабильные структуры данных, функция, изменяющая переменную, зачем тогда функциональщина?

Это называется append :)

А что ты в конец добавляешь, e или следующее за ней?

Типа бесконечных коллекций.

В бесконечной коллекции в конец нет смысла добавлять ничего ;)

ой да ладно, вот держи -

let iter seq = 
    match seq with
    | h :: t ->
        iter(append(t, next(h)))
    | [] -> null

Где мутабельность? Меня интересует - неужели в ФП нет специальной абстракции для таких вычислений?

Блин, так бы сразу и сказали. На Haskell:

newSeq = amend seq where
  amend [] = []
  amend seq' = seq' ++ amend (map next (filter test seq'))

Или без явной рекурсии (что всегда предпочтительнее):

newSeq = concat $ takeWhile (not . null) $ iterate (map next . filter test) $ seq

хоть бы пояснил как нибудь, это ведь ЯП с одним из самых высоких порогов вхождения... Но в общем-то непонятно amend - это список или функция? То есть я могу написать что-то типа -

 
(map print (amend [1; 2; 3]))

а в чем идея-то, для тех кто не знаком с Haskell?

Но в общем-то непонятно amend - это список или функция?

Функция. С аргументом seq'.

(map print (amend [1; 2; 3]))

print (amend [1,2,3])

и он тебе всё выведет. Или, если хочешь выводить построчно, тогда

mapM_ print (amend [1,2,3])

Списки в хаскеле вообще ленивые, я не очень понял вопрос.

а в чем идея-то, для тех кто не знаком с Haskell?

Смотри. Пусть у нас есть некий список seq. Если мы сделаем filter test seq, то получим список из тех элементов, для которых test даёт True. Если мы сделаем map next seq, то получим список, где ко всем элементам seq применена функция next. Нам нужно и то, и другое — точнее, нам нужна композиция: сначала отфильтровать, потом сделать map. Композиция функций в Хаскеле делается оператором (.). То есть, то, что нам нужно, получается из seq применением функции «map next . filter test».

Теперь дальше. iterate делает из функции и аргумента список — сначала идёт сам аргумент, затем — функция, применённая к этому аргументу, затем — функция, применённая к результату, и так далее. Короче,

iterate f a = [a, f a, f (f a), f (f (f a)),...]

Далее. Функция null проверяет, является ли список пустым. Функция not — ну, это булевский not. Так что (not . null) проверяет, является ли список НЕпустым (опять композиция). Функция takeWhile берёт из списка префикс, состоящий из элементов, удовлетворяющих условию; как только она встречает элемент, условию не удовлетворяющий — останавливается. То есть, takeWhile (not . null) $ something выберет из списка списков something первые непустые.

Наконец, concat берёт список списков и просто соединяет его элементы.

Конкретный пример. Допустим, test — это проверка, что число НЕ делится на 3, а next — это прибавление 1. Пусть seq — это список [3,11,25]. Тогда

seq = [3,11,25]
filter test seq = [11, 25]
map next (filter test seq) = [12, 26]
map next $ filter test seq = [12, 26]
map next $ filter test $ seq = [12, 26] -- короче, это всё одно и то же.
(map next . filter test) seq = [12, 26]
filter test $ (map next . filter test) seq = [26]
map next $ filter test $ (map next . filter test) seq = [27]
(map next . filter test) $ (map next . filter test) seq = [27]
filter test $ (map next . filter test) $ (map next . filter test) seq = []
(map next . filter test) $ (map next . filter test) $ (map next . filter test) seq = []
-- дальнейшие итерации тоже дают []
iterate (map next . filter test) seq = [[3,11,25],[12,26],[27],[],...]
null [3,11,25] = False
not (null [3,11,25]) = True
(not . null) [3,11,25] = True
(not . null) [12,16] = True
(not . null) [27] = True
(not . null) [] = False
takeWhile (not . null) [[3,11,25],[12,26],[27],[],...] = [[3,11,25],[12,26],[27]]
takeWhile (not . null) $ iterate (map next . filter test) seq = [[3,11,25],[12,26],[27]]
concat [[3,11,25],[12,26],[27]] = [3,11,25,12,26,27]
concat $ takeWhile (not . null) $ iterate (map next . filter test) seq = [3,11,25,12,26,27]

http://erlang.org/doc/man/queue.html

Супер, просто супер. А iterate как по-научному называется? Это как раз пример бесконечного рекурсивного типа, про который я спрашивал в предыдущем топике - Генератор на функциях в F# . В F# я не могу использовать функции с типом, который нельзя полностью вычислить на момент компиляции, а в Haskell для этого есть специальные механизмы типа iterate?

Тогда, чтобы до конца убедиться в правильности понимания, я могу бы использовать этот код наподобие? -

// pseudo code
data = [7; 1; 5; 4; 10]
next x =
    filter (nx -> |x - nx| <= 3.0) data
//--- 
intervalSortedSeq = concat $ takeWhile (not . null) $ iterate (map next) $ [0]

// sortedSeq : [[0] @ [1] @ [4] @ [5, 7] @ [10]] = [0 1 4 5 7]

А iterate как по-научному называется?

Называется «iterate».

Это как раз пример бесконечного рекурсивного типа

Нет тут никакого рекурсивного типа. iterate — обычная функция с типом

iterate :: (a -> a) -> a -> [a]

data = [7; 1; 5; 4; 10]

Только с запятыми:

data = [7,1,5,4,10]

next x = filter (nx -> |x - nx| <= 3.0) data

Стоп-стоп-стоп. next должно быть функцией типа «a -> a» (для какого-то a). То есть, если, как в данном случае, аргументом являются числа, то next x тоже должно быть числом.

Или ты хочешь, чтобы next возвращало не одно значение, а список значений? Если так, то код будет чуть другой, простейший вариант — заменить функцию map на concatMap (хотя уважающий себя хаскельщик написал бы не «concatMap next», а "(>>= next)").

Или я тебя как-то не так понял? И откуда у тебя взялось nx?

Или я тебя как-то не так понял?

я не понял вот это:

iterate f a = [a, f a, f (f a), f (f (f a)),...]

Таким образом, если мы сделаем iterate (map next . filter test) seq (знак $ тут не обязателен, стоит для красоты — он означает просто применение функции к аргументу, но со специальным приоритетом), то получим список, элементами которого будут списки: сначала — сам seq, затем — то, что из него получается, если отфильтровать и применить next, затем — то, что получается из этого той же операцией, и так далее.

то есть a - это начальная последовательность, f a - это последовательность после применения к каждому элементу next и так далее. То есть f имеет тип seq -> seq? Тогда я вроде могу написать так -

// pseudo code
data = [7; 1; 5; 4; 10]
next x =
    filter (nx -> |x - nx| <= 3.0) data
//--- 
intervalSortedSeq = concat $ takeWhile (not . null) $ iterate  next $ [0]

// sortedSeq : [0] @ [1] @ [4] @ [5, 7] @ [10] = [0 1 4 5 7]

И откуда у тебя взялось nx?

это аргумент анонимной функции

(nx -> |x - nx| <= 3.0)

То есть f имеет тип seq -> seq?

Ну да.

это аргумент анонимной функции

А, кажется, понял. То есть, в хаскельной записи

filter (\nx -> abs (x - nx) <= 3) data

«next» это «f» в записи «iterate f a», или результат композиции функций map, next и filter из твоего примера(так проще для понимания в начале). Но в целом это очень похоже на лисповский loop:

(loop for a = [1] next (mapcar #'next a)
      do ...)

Ничего не понимаю.

У ТЕБЯ в постановке задачи есть некая функция next. Что она возвращает? Одно значение, или целый список?

очереди LIFO

Так очереди — или LIFO? LIFO — это стек.

по сути это просто рекурсия в разных видах

Так всё — рекурсия в разных видах.

вот конкретно твой код это всего лишь.

mkSeq :: (a -> Bool) -> (a -> a) -> [a] -> [a]
mkSeq _ _ [] = []
mkSeq pred next initial = initial ++ mkSeq pred next [next x | x <- initial, pred x]

на выходе выдаст «модифицированную» коллекцию.

что практически совпадает с вариантом с iterate, разве, что остановится в конце коллекции.

Вариант с iterate тоже остановится. Зря я, что ли, takeWhile впендюрил?

У ТЕБЯ в постановке задачи есть некая функция next. Что она возвращает? Одно значение, или целый список?

возвращает список.

На самом деле идея, про которую я толдычу очень проста, вот смотри, к примеру, описание DBSCAN в вики - https://en.wikipedia.org/wiki/DBSCAN

expandCluster(P, NeighborPts, C, eps, MinPts) {
   add P to cluster C
   for each point P' in NeighborPts { 
      if P' is not visited {
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      }
      if P' is not yet member of any cluster
         add P' to cluster C
   }
}

Если читал SICP, там описывается программа для эмуляции работы эл. схем, в которой используется расписание и «время» в виде условно бесконечного списка. Просто идея интуитивно понятнее рекурсии и всяких там генераторов, но вот так как есть я не видел её реализации, потому и интересуюсь.

тогда ж `unfoldr` проще?

P.S. врочем там уже ньюансы всякие, может и не проще оказаться.

тогда ж `unfoldr` проще?

По-моему, нет. iterate и takeWhile заметно проще, и, когда можно обойтись ими, лучше обойтись.

Вот, скажем, числа Хэмминга считать — это да, тут unfoldr ближе всего будет.

hammings =
  1 :
  unfoldr
    (\hss -> 
       let x = minimum $ map head hss in
       Just (x, map (dropWhile (x ==)) hss))
    (map (\n -> map (n *) hammings) [2,3,5])

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

судя по количеству вопросов к псевдокоду в ТС, он менее интуитивно понятный нежели варианты хацкелистов..

Тебя здесь никто не понял. У обычных людей next это что-то, возвращающее следующий элемент, а что это у тебя - ХЗ.

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

А как это делается на функциональном языке, я тебе продемонстрировал. В чём вопрос-то?

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

extendCluster :: (Point -> [Point]) -> [Point] -> [Point]
extendCluster range =  unfoldr go . (Set.empty,)
   go (_, []) = Nothing
   go (visited, (f:fs))
      | f `V.member` visited = go visited fs
      | otherwise = Just (f, (Set.insert f visited, fs ++ range f))

P.S. а кто-нить кому нечего делать не хочет написать решение через комонады или Fix?