Рекурсия против. Рекурсия хвоста

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

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

(define (alignment-score string_one string_two)
  (if (and (not (= (string-length string_one) 0))
           (not (=(string-length string_two) 0)))
      (+ (scorer (string-ref string_one 0)
                 (string-ref string_two 0))
         (alignment-score-not-tail
          (substring string_one 1 (string-length string_one))
          (substring string_two 1 (string-length string_two))
          )
       )
    0)
)

recursion functional-programming tail
person Curiosity    schedule 31.03.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вот как это будет выглядеть с аккумулятором:

(define (alignment-score s1 s2)
  (define min-length (min (string-length s1) (string-length s2)))
  (let loop ((score 0)
             (index 0))
    (if (= index min-length)
        score
        (loop (+ score (scorer (string-ref s1 index)
                               (string-ref s2 index)))
              (+ index 1)))))

В этом случае score - это аккумулятор, который начинается с 0. У нас также есть index (также начинающийся с 0), который отслеживает, какую позицию в строке нужно захватить. Базовый случай, когда мы достигаем конца любой строки, - это вернуть накопленное на данный момент score.

person Chris Jester-Young    schedule 31.03.2014
comment
Большое вам спасибо :) Думаю, теперь я уловил концепцию. Ваш код имеет смысл. Еще раз спасибо :) - person Curiosity; 31.03.2014

arrow_upward
1
arrow_downward

Просто хотел сделать вариант ответа Криса, который использует списки символов:

(define (alignment-score s1 s2)
  (let loop ((score 0)
             (l1 (string->list s1))
             (l2 (string->list s2)))
    (if (or (null? l1) (null? l2))
        score
        (loop (+ score (scorer (car l1)
                               (car l2)))
              (cdr l1)
              (cdr l2)))))

Нет смысла останавливаться на достигнутом. Поскольку теперь это стало итерацией по списку, мы можем использовать процедуру более высокого порядка. Обычно нам нужен fold-left или foldl, а SRFI-1 - это реализация этого, которая не требует, чтобы списки были одинаковой длины:

; (import (scheme) (only (srfi :1) fold)) ; r7rs    
; (import (rnrs) (only (srfi :1) fold))   ; r6rs    
; (require srfi/1)                        ; racket

(define (alignment-score s1 s2)
  (fold (lambda (a b acc)
          (+ acc (scorer a b)))
        0
        (string->list s1)
        (string->list s2)))

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

person Sylwester    schedule 31.03.2014
comment
Вы можете добавить, что эталонная реализация fold в SRFI / 1 действительно является хвостовой рекурсивной (см. srfi.schemers.org/srfi-1/srfi-1-reference.scm). - person uselpa; 31.03.2014
comment
@uselpa А левый fold всегда будет. Многие реализации предоставляют свои собственные SRFI-1, которые полностью рекурсивны. TRMCO-ed map работает намного лучше, чем в эталонной реализации. - person Sylwester; 31.03.2014
comment
Зачем останавливаться на fold? Вы можете использовать string-fold из SRFI 13 и пропустить string->list шаги. ;-) - person Chris Jester-Young; 23.04.2014
comment
@ ChrisJester-Young string-fold не принимает более одного строкового аргумента, поэтому вы не можете использовать его таким же образом. - person Sylwester; 23.04.2014
comment
@Sylwester Quick, сообщите об ошибке! (Если серьезно, я могу понять, почему наличие более одной строки является проблемой из-за необходимости также иметь возможность указывать параметры начала / конца. Тем не менее, облом.) - person Chris Jester-Young; 23.04.2014