[ФП][Морфизмы] Годная задачка про списки :)

А мне, например, append тоже ни о чем не говорит. Это куда аппенд в начало или в конец?

если тебе append ни о чем не говорит, ты разделом форума ошибся

Если ни о чем не говорит, то смотри http://www.wordreference.com/definition/append

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

1) Самые «ненаркоманские» решения - циклы следующего вида:

let a = []
    b = []
  for-each element in list
    if (predicate element)
       push element a
       push element b

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

2) Предыдущее решение можно, конечно, записать и в итеративно-рекурсивной форме. Но это практически тоже самое.

3) Функция filter (которая выражается через foldr, т.е. катаморфизм для списков):

filter predicate list -- первый список
filter (not . predicate) list -- второй

Тут всё гораздо проще, чем в первом варианте, но в два прохода.

4) Ну и наконец, непосредственно морфизм - катаморфизм, в данном случае свёртка на списке, т.е. foldr:

foldr ,\ a b
        let b1 (first b)
            b2 (rest  b)
          if (p a)
             (a : b1) : b2
              b1 : (a : b2)
      []
      list

;; Например, на CL:

(defun fold-rigth (f i list)
  (reduce f list :from-end t :initial-value i))

(defun filter/2 (p list)
  (fold-rigth #'(lambda (a b)
		  (let ((b1 (car b))
			(b2 (cdr b)))
		    (if (funcall p a)
			(cons (cons a b1) b2)
		        (cons b1 (cons a b2)))))
	      nil
	      list))

Вроде Ъ ФП вариант, но не совсем очевидно.

Вот. И я вопрос этот задал потому, что мне самому не ясно - как писать. Обычные циклы/рекурсии вроде бы очевидны, с другой стороны, решения в духе (3) выглядят лучше, но они не оптимальны. А вот до решений в духе (4) приходится додумываться.

Почему вы не пишите:

(setf (symbol-function 'filter)
      (symbol-function 'remove-if))

Вроде Ъ ФП вариант

ты извини, конечно,- но это говно, а не вариант

partition :: (a -> Bool) -> [a] -> ([a],[a])
{-# INLINE partition #-}
partition p xs = foldr (select p) ([],[]) xs

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

это реализация из GHC, и она, мягко говоря, читаемей твоей

partition p xs = foldr (select p) ([],[]) xs 
 
select p x ~(ts,fs) | p x       = (x:ts,fs) 
                    | otherwise = (ts, x:fs)

это если по существу

Ты 20 минут думал над тем, как реализовать partition с помощью сверток?

Видимо, это ваш клиент.

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

я это «vs морфизмы» запомню

А как правильно сказать? Я думал когда говорят «морфизм» в контексте «циклы/рекурсия», то имеют в виду какой-нибудь примитив из «бананов, линз, конвертов и колючей проволоки».

Можно ещё гвозди забивать инструментом, работающим на давлении света.

читаемей твоей

Ок, посмотрим.

Я и правда 20 минут думал, т.к. с понятием свёртка познакомился не так давно и вообще не пробовал её применять.

Если бы я просто прочёл prelude, то конечно бы не спрашивал :)

читаемей твоей

Ок, посмотрим.

Короче - читабельней из-за pettern-matching, в моей псевдо-записи его нет, так что не надо говорить «Г» :)

А ты скажи честно - сколько сам думал (если, конечно, просто не посмотрел в prelude). С перерывами на заваривание чая, и вдумчивым рисованием схемы для foldr на листочке.

когда говорят «морфизм» в контексте «циклы/рекурсия»

морфизм - это очень слабая абстракция: стрелка или отображение, сохраняющее структуру из выбранного universe of discourse; как следствие, употребление этого слова наравне с более конкретными понятиями выглядит бессмысленно. если ты хотел сказать «выразить через свёртку» (ну или катаморфизм, если тебе это слово больше по душе), то так и надо было говорить

с понятием свёртка познакомился не так давно и вообще не пробовал её применять.

ну имей в виду, что чем явственней виден моноид (множество, бинарная операция, нейтральный элемент) в твоей свёртке, тем лучше. читать лямбда-портянки - сложно

>Просто, понятно, в один проход. Но используются побочные эффекты и «многабукаф»

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

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

Вот. И я вопрос этот задал потому, что мне самому не ясно - как писать. Обычные циклы/рекурсии вроде бы очевидны, с другой стороны, решения в духе (3) выглядят лучше, но они не оптимальны. А вот до решений в духе (4) приходится додумываться.

Всего два варианта - производительность (1-2) или краткость кода (3). Обычно производительность важнее, благо код в (1-2) не длинный.

Всего два варианта - производительность (1-2) или краткость кода (3)

и чем решение со свёрткой будет хуже (1-2) в смысле производительности?

Какие, нафиг, побочные эффекты?

push выражается через присваивания. В FP-like вариантах нет присваивания.

Всего два варианта - производительность (1-2) или краткость кода (3). Обычно производительность важнее, благо код в (1-2) не длинный.

Скажем так - (1) производительность.

(2) - тоже, но при соблюдении TCO.

Причём в реальном коде краткостью и не пахнет.

(3-4) - краткость (jtootf, уже написал 4 вариант «как надо»). Относительно - производительности:

? Как при наличии функций с побочными эффектами как мне детектировать холостые циклы.

? Как мне распараллелить цикл если в нём есть побочные эффекты.

И то и другое возможно в случае чистых функций и свёрток.

;; Например, на CL:

Поправка:

;; lib.

(defun fold-rigth (f i list) 
  (reduce f list :from-end t :initial-value i))

(defun select (p)
  (lambda (e list)
    (if (funcall p e)
        (cons (cons e (car list)) (cdr list))
        (cons (car list) (cons e (cdr list))))))

;; one line

(defun partition (p list) (fold-rigth (select p) nil list))

;; vs.

(defun partition (p list)
  (let (L1 L2)
    (dolist (e list)
      (if (funcall p e)
          (push e L1)
          (push e L2)))
    (values (nreverse L1) (nreverse L2))))

;; or

(defun partition (p list)
  (loop :for e :in list 
        :when (funcall p e) :collect e :into L1
        :else               :collect e :into L2
        :finally (return (values L1 L2))))

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

И вправду - loop будет работать быстрее dotimes т.к. делает декларации типов, знает где списки и может генерировать (declare (type list ...))

dotimes будет работать лучше только если прописать типы:

(defun partition (p list)
  (declare (type function p) (type list list))
  (let (L1 L2)
    (declare (type list L1 L2))
    (dolist (e list) 
      (if (funcall p e) 
          (push e L1) 
          (push e L2))) 
    (values (nreverse L1) (nreverse L2))))

А вариант через fold-right (т.е. через reduce) работает всего в 2 (!) раза медленнее (SBCL), по крайней мере на этой задаче.

s/dotimes/dolist/

> Можно ещё гвозди забивать инструментом, работающим на давлении света.

ТС, залогинься. И давай уже dropWhile в студию. partition — это так, детские шалости.

ТС, залогинься.

Ну я как бы уже переквалифицировался в штат пользователей с nick /= nil

И давай уже dropWhile в студию. partition — это так, детские шалости.

Как раз, если через `cata', то различий между ними почти нет:

;;; lib.

(defun fold-rigth (f i list)
  (reduce f list :from-end t :initial-value i)) 
 
(defun select (p)
  (lambda (e list) 
    (if (funcall p e) 
        (cons (cons e (car list)) (cdr list)) 
        (cons (car list) (cons e (cdr list)))))) 

(defun drop (p)
  (lambda (e list)
    (if (funcall p e) 
	(cons (car list) (car list))
        (cons (cons e (cdr list)) (cons e (cdr list))))))

;;; а какая разница? немножко по-другому обновлять списки в комбинациях F в foldr

(defun partition  (p list) (fold-rigth (select p) nil list)) 
(defun drop-while (p list) (car (fold-rigth (drop p) nil list)))

Но вот можно сделать ещё через `para':

(defun para (f e list)
  (typecase list
    (null e)
    (cons (funcall f (car list) (cdr list) (para f e (cdr list))))))

(defun drop (p)
  (lambda (e L1 L2)
    (if (funcall p e)
	L2
        (cons e L1))))

(defun drop-while (p list) (para (drop p) nil list))

Как насчёт сделать срез списка черёз свёртку?)

Короче - читабельней из-за pettern-matching, в моей псевдо-записи его нет, так что не надо говорить «Г» :)

Не только и не столько. Вот без:

partition p xs = foldr (select p) ([],[]) xs  
  
select p x ~(ts,fs) = if p x then (x:ts,fs)
                             else (ts, x:fs)

Scala

object Main{
	def partition[T](f:(T)=>Boolean,a:List[T]) ={
		var l1 = List[T]();	var l2 = List[T]();
		for (val i <- a) if (f(i)) 
			l1=i::l1 else l2=i::l2
		(l1,l2)
	}

	def main(args: Array[String])={
		val (l1,l2) = partition ( (a:Int) => a >= 5, List(2,4,56,7,8,9))
		println(l1);
		println(l2);
	}
}

Или конечно

def partition2[T](f:(T)=>Boolean,a:List[T]) =  (a filter f, a filter {(m:T) => !f(m)} )

Но это два прохода

Ну и я забыл сказать. partition уже готов и есть методом класса List

override def	partition (p : (A) => Boolean) : (List[A], List[A])

Ещё выделение лямбды в select (кто ж знал что это сущность имеет смысл вне partition?), инфиксные операторы и tuples отделённые от lists.

Вот ещё большее наркоманство:

partition p xs = foldr (select p) nil xs   
select p x (ts fs) = (come-false (come-true (p x) ((x : ts) : fs)) (ts : (x : fs)))

А как будет выглядеть вариант через свёртку?

А вообще, даже на Си можно реализовать все 4 варианта. Интересно именно предпочтения, и вопросы из серии краткость/производительность. Как я понимаю в этом вопросе нет согласия.

(drop-while #'(lambda (x) (= (mod x 2) 0)) '(1 2 3 4 5 6 7))

(1 3 5 7)

Это не dropWhile, это filter.

Это какой-то тонкий юмор?

Ага, тупо фильтр получился, хотя с `para' работает правильно. Но всё равно - отличий мало, нужно только правильно передавать списки списков :)

(defun drop (p) 
  (lambda (e list) 
    (if (funcall p e)
        -(cons (car list) (car list)) 
        -(cons (cons e (cdr list)) (cons e (cdr list)))))) 
        +(cons (cons e (car list)) (cdr list))
        +(cons (cons e (car list)) (cons e (car list))))))

-(defun drop-while (p list) (car (fold-rigth (drop p) nil list))) 
+(defun drop-while (p list) (cdr (fold-rigth (drop p) nil list))) 

Я вполне серьёзно, хотя точно не представляю - про что говорю :)

Это уже больше похоже на правду, хотя и весьма трудоемкое решение. Сколько времени заняло?

Я не увидел большой разницы, на самом деле.

Я не увидел большой разницы, на самом деле.

между чем и чем?

Примерно столько же - на английской педии есть хорошая картинка.

Я почему-то думал, что фолдящаяся функций это функция от двух «соседних» элементов в списке, в то время как fold это фактически последовательность фильтров (как в электронике) каждый их которых принимают текущий элемент и информацию о всех предыдущих преобразованиях, т.е. тот list можно использовать для хранения абсолютно произвольной информации о том что было и о том что сделано. Поэтому получается выражать через свёртку всякие хитрие вещи - от filter, map, partition и drop-while, до функции доступа к n-ому элементу списка или функции среза списка. Нельзя только делать преобразования, требующие информации о тех элементах, что «дальше» по порядку свёртки.

Вот, можно делать почти всё то, что и циклами (те самые 90%).

Кстати, я тут почитал - оказывается этот drop-while это следствие одной теоремы, которую сформулировали только в 90-ые годы ;)

Между твоим вариантом и квазимодовским.

Между твоим вариантом и квазимодовским.

во-первых, вариант не мой (хотя я бы делал так же); во-вторых, ничем не могу помочь

Чиво только ламиры не делают чтобы STL не использовывать.

Ну, я просто высказал свое видение ситуации

квазимодовским

квазимо_т_овским, же :(

> Кстати, я тут почитал - оказывается этот drop-while это следствие одной теоремы, которую сформулировали только в 90-ые годы ;)

Как интересно. И что это за теорема?

Извиняюсь

И что это за теорема?

Функция dropWhile может быть определена в терминах свёртки. Далее, согласно более общей теореме (Meertens, L. (1992) Paramorphisms. Formal Aspects of Computing, 4(5), 413–425.), любая функция от конечных списков составляющая пару из желаемого результата и параметров списка, всегда может быть определена в терминах свёртки, но это не всегда бывает удобно т.к. оригинальное определение (возможно рекурсивное) может иметь более понятную запись.

Отсюда:

http://www.cs.nott.ac.uk/~gmh/fold.pdf

И есть даже перевод:

http://ru.wikibooks.org/wiki/%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80%D0%B0_%D1%81%D0%B2%D1%91%D1%80%D1%82%D0%BA%D0%B8

Короче, понятно. Подсмотрел в викибуках решение. Ну, дело хозяйское.

http://comonad.com/reader/2009/recursion-schemes/

чего-то мне кажется, что тебе это будет по нраву