U redu, hajde da počnemo kako pronaći podniz unutar niza u Haskell-u.
Haskell je čisto funkcionalni programski jezik poznat po visokom nivou apstrakcije i izražajne sintakse. Jedan uobičajeni zadatak kada se radi sa stringovima je pronalaženje podniza unutar većeg niza – to jest, identificiranje tačne pozicije na kojoj se pojavljuje određeni niz znakova.
U tu svrhu možemo iskoristiti dvije ugrađene Haskell funkcije: `isPrefixOf` i `tails`. `isPrefixOf` provjerava da li je lista prefiks druge liste, a `tails` generira sve završne dijelove liste. 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 i string u kojem tražimo, respektivno.
- Prvo, `tails str` generira sve moguće završetke `str`. Na primjer, s obzirom na string “hello”, `tails` bi generirao [“hello”, “ello”, “llo”, “lo”, “o”, “”].
- Zatim, `map (isPrefixOf substr)` primjenjuje funkciju `isPrefixOf substr` na svaki element liste koju proizvodi `tails str`. Ovo daje listu Booleovih vrijednosti, od kojih svaka pokazuje da li je `substr` prefiks odgovarajućeg elementa u originalnoj listi.
- Konačno, `elemIndex True` pretražuje ovu listu Booleana za prvo pojavljivanje `True`, što odgovara poziciji `substr` u `str`, i vraća ga umotanog u tip podataka `Možda`.
Ključne funkcije i biblioteke
Data.List je Haskell biblioteka prepuna korisnih funkcija za manipulisanje listama. Između ostalog, izvozi funkcije `isPrefixOf`, `tails` i `elemIndex` koje smo koristili u našem rješenju.
Funkcija `isPrefixOf` je posebno ključna za naše rješenje. Provjeravanjem da li je naš ciljni podniz prefiks svake podliste, u suštini provjerava svaku moguću početnu poziciju našeg podniza unutar originalnog niza.
Ekstrapolacije i varijante
Ovaj jednostavan pristup može se ekstrapolirati za obavljanje složenijih zadataka, kao što je pronalaženje svih pojavljivanja podniza, zamjena podniza drugim nizom ili razbijanje niza na komade na osnovu graničnika.
Kao primjer, da biste zamijenili sva pojavljivanja podniza, možete koristiti `intercalate` iz Data.List za spajanje dijelova dobivenih razbijanjem originalnog niza na pozicijama ciljnog podniza.
Uprkos svojoj inherentnoj jednostavnosti i ekspresivnosti, Haskellov pristup obradi stringova pokazuje moć funkcionalnog programiranja u rješavanju uobičajenih zadataka na čist, čitljiv i koncizan način.
