Predikáty foldL a foldR

V tomto odstavci si ukážeme možnost jak vytvořit obecný predikát, který je schopen opakovaně aplikovat binární operaci na prvky seznamu a její výsledky postupně akumulovat. Protože je třeba rozlišit, zda se má daná binární operace asociovat zleva nebo zprava, k vyjádření této akumulované aplikace na prvky seznamů slouží dva predikáty vyššího řádu foldL/4 a foldR/4.

Predikát foldL(+Fun, +List, +IniAcc, -Acc), kde $Fun$ je název predikátu arity $a\ge 3$ a $List$ je seznam s $n$ položkami, provádí akumulovaný průchod seznamu zleva s postupnou aplikací $Fun$. Raději než slovně vyjádříme jeho výsledek schematicky a to takto:

foldL(f,i,[a1,a2,...,an],X) $\rightarrow$ X=f(...(f(f(i,a1),a2)...),an)

kde $i$ je obvykle levou jednotkou vzhledem k operaci $f$.

Samotný predikát je implementován pomocí akumulátoru:

foldL(F,InVal,[I|IT],Out):-
        :-@ [F,InVal,I,OutVal],
        foldL(F,OutVal,IT,Out).
foldL(_,Out,[],Out).

Predikát foldR(+Fun, +List, +IniAcc, -Acc) má stejné argumenty jako foldL/4. Aplikuje však danou operaci s levou asociativitou:

foldR(f,i,[a1,a2,...,an],X) $\rightarrow$ X=f(a1,f(a2,...,f(an,i)...))

kde $i$ je stejně jako minule obvykle pravá jednotka vzhledem k operaci $f$.

foldR( F, InVal, [I|IT], Out ):-
        foldR( F, InVal, IT, OutVal ),
        :-@ [F,I,OutVal,Out].	
foldR( _, InVal, [], InVal ).