[room] Вопрос по Lisp

[Alexey Voinov]

Денис Смирнов <mithraen на altlinux.ru> writes:

> Так и не смог нормально в Lisp решить задачу:
>
> Имеется массив с числами. Надо для него сделать что-то вроде trim --
> получить второй массив, который бы не содержал завершающих нулей.
>
> Я понимаю как её решить тупо (одним циклом для поиска новой длины, потом
> создать новый массив, и также циклом перенести данные), но это же кошмар а
> не код!
Не, ты не понимаешь. :) Тупо - это вот так  (используем srfi-1):

(define (trim-zeroes-right data)
  (reverse (drop-while zero? (reverse data)))

Здесь по сути два полных прохода по списку и один проход только по
нулям в хвосте. Памяти требует немного (оно tail-recursive).

Можно это сократить до гарантированных двух проходов, за счёт
несколько более громоздкого кода:

(define (trim-zeroes-right data)
  (let loop ((data   data)
             (result '())
             (zeroes '()))
    (cond ((null? data)       (reverse result))
          ((zero? (car data)) (loop (cdr data)
                                    result
                                    (cons 0 zeroes)))
          ((null? zeroes)     (loop (cdr data)
                                    (cons (car data) result)
                                    zeroes))
          (else               (loop (cdr data)
                                    (cons (car data)
                                          (append zeroes result))
                                    '())))))

А если данные к нам приходят вектором, то получаем один проход по
нулям и одно копирование субвектора (используем srfi-43):

(define (trim-zeroes-right data)
  (let loop ((newlen (vector-length data)))
    (let ((index (- newlen 1)))
      (cond ((zero? newlen)
             '#())
            ((zero? (vector-ref data index))
             (loop index))
            (else
             (vector-copy data 0 newlen))))))

Т.е. последняя функция осуществляет всего один полный проход по всем
элементам. В чём оно принципиально отличается от решения на C, я не
вижу, честно говоря.


> Можно ли такое решить на голом лиспе, или нужно таки не выпендриваться и
> написать на C?

> ----------------------------------------------------------------------------
> <Voins> посади дебианщика за alt так он сразу локали сломает! :)))
Это ты специально фортунку со мной в такое письмо вставил? :))

-- 
Voins