Derivazione Definizione ricorsiva dalla specifica delle funzioni

Question

Dato questa funzione Specifica, in cui il nome xs è associato a un elenco, # denota la sua cardinalità e . è l'operatore list index ...

$$ \ sinistra (\ somma I: 0 \ leq i <\ #xs: xs.i * (i + 1) \ destra) $$ < / P >.

Devo ricavare una funzione ricorsiva usando l'induzione.

Caso base: []

\ begin {allinea} \ Sinistra (\ Sum I: 0 \ Leq I <\ # []: xs.i * (i + 1) \ destra) && \ text {(sostituzione testuale - xs è gratuito)} \\ \ Sinistra (\ Sum I: 0 \ Leq I <0: XS.I * (I + 1) \ Destra) && \ text {(def. di #)} \\ \ Sinistra (\ Sum I: False: xs.i * (I + 1) \ destra) && \ text {(algebra)} \\ \ Sinistra (\ Sum I: 0 \ Leq I <\ #xs: xs.i * (i + 1) \ destra) && \ text {(intervallo vuoto)} \ end {allinea}

Cassa induttiva: (x:xs)

\ begin {allinea} \ Sinistra (\ Sum I: 0 \ Leq I <\ # (x: XS): (x: XS) .I * (I + 1) \ destra) && \ text {(sostituzione testuale - xs è gratuito)} \ \ \ Sinistra (\ Sum I: 0 \ Leq I <1 + \ #XS: (X: XS) .I * (I + 1) \ Destra) && \ text {(def. di #)} \ end {allinea}

Come posso procedere da qui?

Answer 1

La tua notazione e la tua comprensione sono piuttosto buone.

È più facile considerare (xs:x) come caso induttivo invece di (x:xs)

\ begin {allinea} \ sum_ {i: \ 0 \ leq i <\ # (xs: x)} & (xs: x) .i * (I + 1) \\ &=Sum _ {i: \ 0 \ Leq I <\ # XS + 1} (X: XS) .I * (I + 1) \\ &=sum_ {i: \ 0 \ leq i <\ 0 \ leq i <\ #xs} (xs: x) .i * (i + 1) + \ sum_ {i: \ i=# xs} (xs: x) .i * (I + 1) \\ &=sum_ {i: \ 0 \ leq i <\ 0 \ leq i <\ #xs} xs.i * (i + 1) + x * (\ # xs + 1), \\ \ end {allinea} Dove assumiamo che l'indice elenco inizia con 0.

Se indiciamo la funzione di $ f $ , l'uguaglianza di cui sopra diventa $$ f (xs: x)= f (xs) + x * (\ # xs + 1), $$ che è il passo ricorsivo di una definizione ricorsiva.

Il caso base, come hai indicato, è $$ f ([])=sum_ {i: \ 0 \ leq i <0} [] .i * (i + 1)=sum_ {i: \ text { Set vuoto}} []. I * (I + 1)= 0. $$

---

.

Esercizio . Deriva la seguente formula ricorsiva della stessa funzione $ f $ . $$ f (x: xs)= f (xs) + t (xs) + x, $$ dove $$ t (xs)=sum_ {i: \ 0 \ leq i <\ # (xs)} xs.i, $$ La somma degli articoli in $ xs $ .