U redu, počnimo s pronalaženjem podniza unutar niza u Haskell-u.
Haskell je čisto funkcionalni programski jezik poznat po visokoj razini apstrakcije i izražajne sintakse. Jedan uobičajeni zadatak pri radu s nizovima je pronaći podniz unutar većeg niza – to jest identificirati točnu poziciju na kojoj se pojavljuje određeni niz znakova.
U tu svrhu možemo iskoristiti dvije ugrađene Haskell funkcije: `isPrefixOf` i `tails`. `isPrefixOf` provjerava je li popis prefiks drugog popisa, a `tails` generira sve završne dijelove popisa. Također ćemo koristiti funkciju `elemIndex` iz `Data.List` da dobijemo indeks prvog pojavljivanja određenog elementa.
Evo jednostavnog rješenja problema:
import Data.List
findSubstring :: String -> String -> Maybe Int
findSubstring substr str =
elemIndex True $ map (isPrefixOf substr) (tails str)
Djelovanje Kodeksa
Funkcija `findSubstring` uzima dva argumenta, `substr` i `str`, koji predstavljaju podniz koji tražimo odnosno niz koji tražimo.
- Prvo, `tails str` generira sve moguće završetke `str`. Na primjer, s obzirom na niz "hello", `tails` bi generirao ["hello", "ello", "llo", "lo", "o", ""].
- Zatim, `map (isPrefixOf substr)` primjenjuje funkciju `isPrefixOf substr` na svaki element popisa koji proizvodi `tails str`. Ovo daje popis Booleovih vrijednosti, od kojih svaka pokazuje je li `substr` prefiks odgovarajućeg elementa u izvornom popisu.
- Konačno, `elemIndex True` pretražuje ovaj popis Booleovih vrijednosti za prvo pojavljivanje `True`, što odgovara položaju `substr` u `str`, i vraća ga zamotanog u tip podataka `Maybe`.
Ključne funkcije i biblioteke
Podaci.Popis je Haskell biblioteka prepuna korisnih funkcija za manipuliranje popisima. Između ostalog, eksportira funkcije `isPrefixOf`, `tails` i `elemIndex` koje smo koristili u našem rješenju.
Funkcija `isPrefixOf` posebno je ključna za naše rješenje. Provjerom je li naš ciljni podniz prefiks svake podliste, u biti se provjerava svaka moguća početna pozicija našeg podniza unutar izvornog niza.
Ekstrapolacije i varijante
Ovaj jednostavan pristup može se ekstrapolirati za izvođenje složenijih zadataka, kao što je pronalaženje svih pojavljivanja podniza, zamjena podniza drugim nizom ili razbijanje niza na dijelove na temelju graničnika.
Na primjer, da biste zamijenili sva pojavljivanja podniza, mogli biste upotrijebiti `intercalate` iz Data.List za spajanje dijelova dobivenih razbijanjem izvornog niza na položajima ciljnog podniza.
Unatoč svojstvenoj jednostavnosti i izražajnosti, Haskellov pristup obradi nizova prikazuje snagu funkcionalnog programiranja u rješavanju uobičajenih zadataka na čist, čitljiv i sažet način.
