Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Kombinatoorsed funktsioonid Alljärnevalt defineeritud funktsioonid opereerivad listidega. Nende kõigi tulemuseks on listide listid, kusjuures listielementide spetsiifilisi omadusi ei kasutata. Ainukene mida need funktsioonid teevad on kas mingite elementide eemaldamine, loendamine või äravahetamine. > module ListComb where 1. Listi prefiksid ja sufiksid ------------------------------ > inits, tails :: [a] -> [[a]] Funktsioonid inits ja tails leiavad vastavalt etteantud listi kõik prefiksid ja sufiksid. Seejuures loeme, et ka tühi list on suvalise listi prefiksiks või sufiksiks. Seega on tühjal listil täpselt üks prefiks/sufiks - tema ise: inits [] = [[]] tails [] = [[]] Mittetühja listi (x:xs) jaoks vaatame näiteid: inits [1,2,3,4] ==> [[], [1], [1,2], [1,2,3], [1,2,3,4]] inits [2,3,4] ==> [ [], [2], [2,3], [2,3,4]] tails [1,2,3,4] ==> [[1,2,3,4], [2,3,4], [3,4], [4], []] tails [2,3,4] ==> [ [2,3,4], [3,4], [4], []] Paneme tähele, et alates teisest listi (inits [1,2,3,4]) elemendist, langevad kõik listi (inits [2,3,4]) elemendid kokku vastavate elemntide sabadega. Seejuures on listide peadeks argumendina saadava listi pea. Seega sobib prefiksite joaks järgmine definitsioon: > inits [] = [[]] > inits (x:xs) = [] : map (x:) (inits xs) Funktsiooni tails korral on olukord veelgi lihtsam, kuna esimese listi saba langeb teise listiga täpselt kokku. Seega: > tails [] = [[]] > tails (xs@(_:xs')) = xs : tails xs' 2. Listi segmendid ------------------ > segs :: [a] -> [[a]] Funktsioon segs leiab etteantud listi kõik segmendid; so. kõik sellised alamlistid, mille järjestikku olevad elemendid on ka esialgses listis järjestikku. Näiteks: segs [1,2,3,4] ==> [[], [4], [3], [3,4], [2], [2,3], [2,3,4], [1], [1,2], [1,2,3], [1,2,3,4]] Tühja listikorral olukord täpselt sama, mis kahel eelmisel korral. Mittetühja listi jaoks katsetame juba äraproovitud meetodi: segs [ 2,3,4] ==> [[], [4], [3], [3,4], [2], [2,3], [2,3,4]] Nagu näha, langeb esimene pool listist (segs [1,2,3,4]) täpselt kokku listiga (segs [2,3,4]). Teises pooles aga paneme tähele, et tegu on listi prefiksitega (välja arvatud tühiprefiks, mis juba esines esimeses pooles). Seega: segs [] = [[]] segs (x:xs) = segs xs ++ tail (inits (x:xs)) Toodud definitsioonis genereerib inits kõigepealt tühja listi, mis seejärel kohe ära visatakse. Asendades funktsiooni inits esinemise tema definitsiooniga ja seejärel lihtsustades, saame natuke efektiivsema definitsiooni: > segs [] = [[]] > segs (x:xs) = segs xs ++ map (x:) (inits xs) 3. Alamlistid ------------- > subs :: [a] -> [[a]] Funktsioon subs leiab listi kõik alamlistid. Tühja listi ainukeseks alamlistiks on ta ise; mittetühja listi (x:xs) korral on kahesuguseid alamliste: a) need mille pea ei ole x; järelikult on nad argumentlisti (x:xs) saba xs alamlistid; b) need mille pea on x; nende saba peab samuti olema argumentlisti saba alamlist. Seega saame järgmise definitsiooni subs [] = [[]] subs (x:xs) = map (x:) (subs xs) ++ subs xs Paneme tähele, et toodud definitsiooni teise võrrandi paremas pooles esineb funktsioon subs kaks korda, kusjuures mõlemad on rakendatud samale argumendile. Selle tulemusena arvutatakse listi xs alamlistide list välja kaks korda ning toodud definitsioon on eksponentsiaalse keerukusega. Selle vältimiseks võime kasutada where-konstruktsiooni: > subs [] = [[]] > subs (x:xs) = map (x:) subsxs ++ subsxs > where subsxs = subs xs On lihtne veenduda, et toodud definitsioon on lineaarse keerukusega. 4. Elemendi sisestamised ------------------------ > interleave :: a -> [a] -> [[a]] Funktsioon inetrleave saab mingi elemendi ja sama tüüpi listi ning väljastab selle elemendi kõikvõimalikud sisestused antud listi. Tühja listi korral on võimalik ainult üks sisestus, so. antud elemendist koosnev üheelemendiline list. Mittetühja listi korral on kaks varianti, kas element x on lisatud antud listi esimeseks elemendiks või mitte. Esimene juhtum on triviaalne, teisel juhul lisame elemendi x rekursiivselt argumentlisti sappa ja seejärel lisame iga tulemuslisti esimeseks elemendiks argumentlisti pea. Seega: > interleave x [] = [[x]] > interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys) 5. Permutatsioonid ------------------ > perms :: [a] -> [[a]] Funktsioon perms leiab argumentlisti kõikvõimalikud permutatsioonid. Näiteks: perms [] ==> [[]] perms [1] ==> [[1]] perms [1..3] ==> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Selleks leiame kõikepealt argumentlisti saba permutatsioonid ning seejärel sisestame argumentlisti pea igasse saadud 'sabapermutatsiooni'. Seega: > perms [] = [[]] > perms (x:xs) = concat (map (interleave x) (perms xs)) 6. Kombinatsioonid ------------------ > combs :: Int -> [a] -> [[a]] Funktsioon kombs saab argumentidena täisarvu n ja listi; tulemuseks on argumentlist kõikvõimalikud n-kombinatsioonid. Näiteks: combs 0 [1..3] ==> [[]] combs 1 [1..3] ==> [[1],[2],[3]] combs 2 [1..3] ==> [[1,2],[1,3],[2,3]] combs 3 [1..3] ==> [[1,2,3]] combs 4 [1..3] ==> [] Iga listi korral on 0-kombinatsioone täpselt üks -- tühi list. Kui n on suurem kui listi pikkus, siis n-kombinatsioone ei ole. Muudel juhtudel saab kõik kombinatsioonid jagada kaheks -- need mis sisaldavad argumentlisti pead ja need mis ei sisalda. Esimesel juhul on nende listide sabaks argumentlisti mingi (n-1)-kombinatsioon, teisel juhul on tegemist argumentlist saba n-kombinatsiooniga. Seega: > combs 0 _ = [[]] > combs n [] = [] > combs n (x:xs) = map (x:) (combs (n-1) xs) ++ combs n xs