Q13: inserer_liste

Profil

inserer_liste: liste x entier x liste

Exemples

inserer_liste( (y z), 2, (a b c) ) = (a y z b c)

Il faut créer une nouvelle liste -> on utiliser une fonction auxiliaire

inserer_liste( (y z), 2, (a b c) )
 =  aux( (y z), 2, (a b c), () )
 =  aux( (y z), 1, (b c), (a) )
 =  concatener(concatener( (a), (y z)), (b c))
 =  (a y z b c)
inserer_liste( (y z), 3, (a b c) )
 =   aux( (y z), 3, (a b c), () )
 =   aux( (y z), 2, (b c), (a) )
 =   aux( (y z), 1, ( c ), (a b) )
 =   concatener(concatener( (a b), (y z)), ( c ))
 =   (a b y z c)

Axiomes

inserer_liste(L1, n, L2) = aux(L1, n, L2, liste_vide())
aux(L1, 1, L2, L3) = si_alors_sinon_finsi(concatener(concatener(L3, L1), L2)
n > 1 => aux(L1, n, liste_vide(), L3) = Erreur
n > 1 => aux(L1, n, cons(x,L2), L3) = aux(L1, n-1, L2, snoc(x, L3))