> Возможно ли решить задачу без циклов и дополнительных переменных, пользуясь только рекурсией?

Можно конечно. А в чём проблема-то?

А вот никак не получается красиво. Проблема в том, чтобы _красиво_ написать, т.е. без дополнительных аргументов или переменных. Код изобразите?

вот мой вариант. Хотелось бы избавиться от b0:

(defun mult (a b &optional (b0 b)) (cond ((null a) nil) ((null b) (mult (cdr a) b0 b0)) (t (cons (list (car a) (car b)) (mult a (cdr b) b0)))))

Написать на LISP'е.

>Возможно ли решить задачу без циклов и дополнительных переменных, пользуясь только рекурсией?

А LISP'е разве есть циклы и переменные? Я думал там только константы, функции и рекурсия.

Lisp не знаю, но на Scala, например, это звучит так:

def zip[A, B](l1: List[A], l2: List[B]): List[(A, B)] =
     if (l1.isEmpty || l2.isEmpty) Nil
     else (l1.head, l2.head) :: zip(l1.tail, l2.tail)

Можно экстраполировать это на Lisp

(defun mult (a b) 
  (mapcan (lambda (z) (mapcar (lambda (y) `(,z ,y)) a)) b))

по-моему это не совсем то, т.к. (zip '( 1 2) '(a b) ) выдает ( (1 a) (2 b) )

Мир Лиспа, т.1, с 255.
(defun декартово(x y) 
  (marpcar 
   '(lambda(x)
     (maprcar '(lambda(y) 
               (list x y))
               y))
   x))

Помню, что когда читал МЛ, целый день ломал голову над этим определением. Сейчас всё забыл и придётся снова ломать. :)

> А LISP'е разве есть циклы и переменные? Я думал там только константы, функции и рекурсия.

Вылезайте из криокамеры. В Лиспе давным-давно есть goto.

ок. Эти страшные слова сработали.

(defun декартово(x y) 
  (mapcar 
   #'(lambda(x)
     (mapcar #'(lambda(y) 
               (list x y))
               y))
   x))

Fixed.

Тьфу, блин. А все моя Ъ-привычка не читать текст сообщения,
на которое отвечаю.

def mix[A, B](l1: List[A], l2: List[B]) = for (a <- l1; b <- l2) yield (a, b)

For comprehension --- синтаксический сахар, так что здесь проблем тоже нет.

Я  тогда могу еще короче привести код (Haskell):

mix a b = [(x,y) | x <- a, y <- b]

В Лиспе таких вещей как list или for comprehension нет, да и 
реализовать интереснее безо всякого синтаксического сахара :-)

красиво - это когда написал и умер.

>В Лиспе таких вещей как list или for comprehension нет

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

Мда, в этом одна из проблем с лиспом. Стоит перестать практиковаться и все забывается.

Рекурсия, без переменных и без лямбд:

(define (mix a b)
  (cond
    ((null? a) nil)
    ((null? b) nil)
    (else (cons
      (list (car a) (car b))
      (mix (cdr a) (cdr b))
    ))
  )
)

Уже было, но на Scala, это функция zip, а не декартово произведение списков.

А если "развернуть" реализацию mapcar/mapcan получится ли чистая рекурсия? Вообще говоря, перекрестной рекурсией, используя еще одну пользовательскую ф-ю) можно решить и без mapcar. Но это не совсем по условию. По условию - одна ф-я, без внешних, используя основные лисповые car/cdr/list и т.п.

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

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

(defun mult(x y) (cond ((null x) nil) (t (append (cons-to-all (car x) y) (mult (cdr x) y))))) (defun cons-to-all(x y) (cond ((null y) nil) (t (cons (list x (car y)) (cons-to-all x (cdr y))))))

ПАРСЕР ЛОХ!!!

(defun mult(x y)
(cond 
((null x) nil)
(t (append (cons-to-all (car x) y) (mult (cdr x) y)))))

(defun cons-to-all(x y)
(cond 
((null y) nil)
(t (cons (list x (car y)) (cons-to-all x (cdr y))))))

Тут опять две функции. Хотелось бы увидеть вариант с одним defun (но с eval например) :)

> красиво - это когда написал и умер.

Неее это смерть от энуреза.

Ну так сделай cons-to-all вложенной (flet или labels, не помню какая форма тут нужна). Одной функцией (без вложенных) насколько я понимаю тут не обойтись.

Может кто знает почему время работы рекурсивной реализация функции member и встроенной функции member различается на порядок?


(defun mem-test (el1 el2 lst)
     (member el2
             (member el1 lst :test #'equal) :test #'equal  ))


(defun mem-test-recursive (el1 el2 lst)
  (labels ( 
            (in-list(el lst) 
             ( cond ( (null lst) nil) 
                    ( (equal el (first lst) ) lst ) 
                    (t ( in-list el (rest lst))))))
  ( in-list el2 (in-list el1 lst) )))

(defun mix (w v) (when w (nconc (mi (car w) v) (mix (cdr w) v))))

(defun mi (a v) (when v (cons (list a (car v)) (mi a (cdr v)))))

CL-USER> (mix '(a b c d) '(1 2 3))

((A 1) (A 2) (A 3) (B 1) (B 2) (B 3) (C 1) (C 2) (C 3) (D 1) (D 2) (D 3))