Joan edukira
Ridgun
Euskara
EnglishEspañolPortuguêsSvenskaCatalàGalegoEuskaraItaliano

09 Ridgun Liburua

str lib-a — Testu-manipulazioa, Bilaketa eta Formatu Taularatua

09.1. Zergatik existitzen da str lib-a? (Benetako arazoa eta Ridgun filosofia)

«Zergatik behar dut str lib bat hutsetik Ridgun hutsean idatzia, betiko C liburutegi bat estekatu beharrean?»

Hori da edozein sistema-ingeniarik str-era iristean egiten duen lehen galdera. Eta erantzunak ridgun-libs-en filosofia osoa laburbiltzen du:

Izan gaitezen zintzoak: C lengoaian strtok eta strncpy bidez kateak manipulatzea buffer-gainezkatzeen eta NULL erakusleen arteko mina-zelai batean ibiltzea da, eta beste lengoaia batzuetan hiru pakete inportatzen amaitzen duzu zutabeak lerrokatzeko.

str lib-ak kateak bilatu, moztu, zatitu, elkartu, letra larri/xeheetara bihurtu, $O(\log N)$ bikoizketa bitarrez errepikatu eta betetzeko primitiba huts eta aldaezin guztiak eskaintzen ditu.

Ekosistema tradizional batean, STR domeinuko zereginak ebazteak C-ko kanpo-mendekotasunak arrastatzea, erakusle gordinekin borrokatzea, mota-bihurketa opakuak, egiaztatu gabeko salbuespenak edo zabor-biltzailearen geldialdi ustekabekoak jasatea dakar. Ridgunen, str lib-ak (src/main/ridgun/lib/str.rg) lau printzipio negoziatu ezinekin heltzen dio arazoari:

  1. Deklaratu import str (edo import str as alias) fitxategiaren hasieran: lib bakoitzak module :: str izen-espazioa definitzen du eta --strict moduan hitz anitzeko funtzioei zuriune naturalekin deitzen zaie beti.
  2. Kateatu zure datu-hodiak ezkerretik eskuinera -> bidez: idatzi sarrera lehen urratsa -> bigarren urratsa -> emaitza, erabili (+ _ _ +) maskarak sekuentziak desegituratzeko eta kendu _ = sententzia sekuentzialetan (edo baztertu -> () bidez).
  3. Isats-errekurtsioa TCOrekin (Tail-Call Optimization): str-eko barne-ibilbide guztiak $O(1)$ pila-espazioko begizta natiboetara konpilatzen dira.
  4. Memoria determinista (RMM1 / RMM2): tarteko egitura bakoitza bere azken irakurketa amaitzen den une zehatzean askatzen da, Garbage Collector gabe.

09.2. Artefaktu natiboak, inportazioa eta str APIaren katalogo osoa

ridgun-libs-en, str lehen mailako lib bat da, src/main/ridgun/lib/str.rg bidean kokatua (STR domeinua). stable bundle-ekin konpilatzean, hiru formatu natibotan paketatzen da:

ArtefaktuaBideaHelburua
Ridgun Bundle-atarget/bundles/str.rglibBanaketa eta inportazio zuzena import str bidez
Fitxategi konpilatuatarget/str.rgcridgunc-ek egiaztatutako tarteko artefaktua
ELF64 objektu partekatuatarget/libstr.soC edo libc mendekotasunik gabeko liburutegi dinamiko natiboa

Lib bakoitzak bere izen-espazioa deklaratzen du module :: str bidez: nahikoa da goiburuan import str (edo import str as alias) idaztea eta bere funtzioei zuriune naturalekin (nire funtzioa x) eta -> hodiekin (x nire funtzioa -> emaitza) deitzea.

09.2.1. str-eko familia funtzionalen laburpena

Sinadura / Funtzioa / MotaZer egiten duen eta noiz erabili
str index of : String -> String -> IntAzpikatearen lehen indizea (-1 ez badago / 0 hutsa bada)
str contains / str starts with / str ends withAzpikate, aurrizki eta atzizkien Bool predikatuak
str trim / str trim left / str trim rightASCII zuriuneak kentzen ditu ( , \t, \n, \r)
str split / str lines / str words / str join[String] zerrendan zatitu eta bereizle batekin elkartzen ditu
str replace / str to upper / str to lowerGainjartzerik gabeko ordezkapena eta ASCII letra larri/xeheen bihurketa
str repeat / str pad left / str pad right$O(\log N)$ errepikapena eta zabaleraardatzeko zutabe-betegarria

09.2.2. src/main/ridgun/lib/str.rg-eko mota eta sinadura guztien katalogoa

Jarraian duzu src/main/ridgun/lib/str.rg fitxategian definitutako mota aljebraiko (type), eragile (op ::) eta funtzio-sinadura (fn ::) guztien inbentario osoa (0 mota, 0 eragile eta 42 funtzio):

#Funtzioa / Sinadura (fn ::)Itzulera-mota
1fn :: is ascii space IntBool
2fn :: is ascii lower IntBool
3fn :: is ascii upper IntBool
4fn :: to upper code IntInt
5fn :: to lower code IntInt
6fn :: str index of from String String Int Int IntInt
7fn :: str index of String StringInt
8fn :: str ends with step String String Int IntBool
9fn :: str ends with String StringBool
10fn :: str is empty StringBool
11fn :: first non space idx String Int IntInt
12fn :: last non space end String IntInt
13fn :: str trim left StringString
14fn :: str trim right StringString
15fn :: str trim slice String Int IntString
16fn :: str trim StringString
17fn :: str is blank StringBool
18fn :: str replace step String String String IntString
19fn :: str replace String String StringString
20fn :: str split chars String Int Int [String][String]
21fn :: str split onech loop String Int Int Int Int [String][String]
22fn :: str split loop String String Int Int Int Int Int [String][String]
23fn :: str split step String String Int Int[String]
24fn :: str split String String[String]
25fn :: str join pair step [String] String [String][String]
26fn :: str join pairs [String] StringString
27fn :: str join [String] StringString
28fn :: upper char code String Int IntString
29fn :: upper char slice String IntString
30fn :: str to upper range String Int IntString
31fn :: str to upper StringString
32fn :: lower char code String Int IntString
33fn :: lower char slice String IntString
34fn :: str to lower range String Int IntString
35fn :: str to lower StringString
36fn :: str repeat loop String Int StringString
37fn :: str repeat String IntString
38fn :: pad fill unit StringString
39fn :: str pad left step String Int String IntString
40fn :: str pad left String Int StringString
41fn :: str pad right step String Int String IntString
42fn :: str pad right String Int StringString

09.3. str sakonki esploratzen: Funtzionalitate bakoitzaren urratsez urratseko adibideak

Ez da nahikoa sinadura-taula ikustea: str lib-aren funtzionalitate bakoitza Ridgunen exekutagarriak diren adibide progresiboen bidez esploratuko dugu. Eguneroko bi errezeta taularatuekin hasiko gara eta ondoren xehetasunez ikusiko ditugu src/test/ridgun/test str.rg-en egiaztatutako agertoki funtzional eta muga-kasu guztiak.

09.3.1. 1. adibidea: Fluxu nagusia estilo taularatuan str erabiliz

Ikusi nola Ridgunen = ikurrak eta str bidezko eraldaketa-urratsak taula garbi bat bezala lerrokatuta geratzen diren, beharrezkoak ez diren aldagai aldakorrik edo ezkutuko albo-ondoriorik gabe:

import str

fn :: normalizar cabecera String => String
      normalizar cabecera raw =
        raw str trim -> str to lower -> limpia
        limpia str split " " -> partes
        str join partes "-" -> slug
        str pad right slug 24 "."

09.3.2. 2. adibidea: Konposizio segurua eta muga-kasuen kudeaketa

str lib-eko funtzio oro | guarda boolearrekin eta ridgun-libs-eko gainerako 32 lib-ekin konposatzeko diseinatuta dago:

import str

fn :: extraer dominio String => String
      extraer dominio correo =
        str index of correo "@" -> pos
        | pos < 0   = "sin-dominio"
        | otherwise =
          correo str to lower -> minusc
          str replace minusc "@" " en "

09.3.3. 3. adibidea: Azpikateen bilaketa (str index of), atzizkiak (str ends with) eta hutsik/zurizko predikatuak

Adibide praktiko honetan str bloke funtzional honetan nola portatzen den sakonki aztertzen dugu, sarrera estandarrak, parametro-konbinazioak eta muga-balioak barne:

fn :: test str search and predicates => ()
      test str search and predicates =
        assert equals (str index of "hello world" "world") 6 "AC1: index_of world"
        assert equals (str index of "hello world" "hello") 0 "AC1: index_of hello at 0"
        assert equals (str index of "ababa" "aba") 0 "AC1: index_of returns first occurrence"
        assert equals (str index of "hello" "xyz") (0 - 1) "AC1: index_of missing"
        assert equals (str index of "short" "much_longer_needle") (0 - 1) "AC1: needle longer than haystack -> -1"
        assert equals (str index of "" "a") (0 - 1) "AC1: non-empty needle in empty haystack -> -1"
        assert equals (str index of "" "") 0 "AC1: empty needle in empty haystack -> 0"
        assert equals (str index of "abc" "") 0 "AC1: empty needle -> 0"

        assert true (str ends with "archive.rglib" ".rglib") "AC1: ends_with true"
        assert true (str ends with "exact" "exact") "AC1: ends_with full string"
        assert true (str ends with "any" "") "AC1: ends_with empty suffix true"
        assert false (str ends with "archive.rg" ".rglib") "AC1: ends_with false"
        assert false (str ends with "short" "longer_suffix") "AC1: ends_with suffix longer than string"

        assert true (str is empty "") "AC1: is_empty true"
        assert false (str is empty " ") "AC1: space is not empty"
        assert true (str is blank "") "AC1: empty is blank"
        assert true (str is blank "   \t\n\r ") "AC1: whitespace-only is blank"
        assert false (str is blank "  x ") "AC1: non-whitespace is not blank"
        ()

09.3.4. 4. adibidea: Zuriuneen mozketa (trim, trim left, trim right), ordezkapena (str replace), zatiketa (str split) eta lotura (str join)

Adibide praktiko honetan str bloke funtzional honetan nola portatzen den sakonki aztertzen dugu, sarrera estandarrak, parametro-konbinazioak eta muga-balioak barne:

fn :: test str trim replace and split => ()
      test str trim replace and split =
        assert equals (str trim "  \thi\n\r ") "hi" "AC2: str_trim mixed ASCII whitespace"
        assert equals (str trim "   \t\r\n") "" "AC2: str_trim all whitespace -> empty"
        assert equals (str trim "") "" "AC2: str_trim empty -> empty"
        assert equals (str trim "no_ws") "no_ws" "AC2: str_trim no whitespace"
        assert equals (str trim left "  abc  ") "abc  " "AC2: str_trim_left"
        assert equals (str trim right "  abc  ") "  abc" "AC2: str_trim_right"

        assert equals (str replace "a-b-c" "-" "_") "a_b_c" "AC2: str_replace single char"
        assert equals (str replace "aaaa" "aa" "b") "bb" "AC2: str_replace non-overlapping left-to-right"
        assert equals (str replace "Hello,World" "World" "") "Hello," "AC2: str_replace deletion to empty"
        assert equals (str replace "abc" "" "x") "abc" "AC2: str_replace empty old leaves string unchanged"
        assert equals (str replace "abc" "z" "y") "abc" "AC2: str_replace absent needle"

        assert equals (str split "a,b,c" ",") ["a", "b", "c"] "AC2: str_split comma"
        assert equals (str split "a,,b," ",") ["a", "", "b", ""] "AC2: str_split consecutive and trailing delim"
        assert equals (str split ",a" ",") ["", "a"] "AC2: str_split leading delim"
        assert equals (str split "a::b::c" "::") ["a", "b", "c"] "AC2: str_split multi-char delimiter"
        assert equals (str split "ab" "") ["a", "b"] "AC2: str_split empty delim splits chars"
        assert equals (str split "" "") [] "AC2: str_split empty string with empty delim -> []"

        assert equals (str join [] "::") "" "AC2: str_join empty list"
        assert equals (str join ["only"] "::") "only" "AC2: str_join singleton"
        assert equals (str join ["alpha", "beta", "gamma"] "::") "alpha::beta::gamma" "AC2: str_join 3 items"
        ()

09.3.5. 5. adibidea: ASCII letra larri/xeheen bihurketa (to upper, to lower), $O(\log N)$ errepikapen bitarra (str repeat) eta lerrokatze taularatua (pad left, pad right)

Adibide praktiko honetan str bloke funtzional honetan nola portatzen den sakonki aztertzen dugu, sarrera estandarrak, parametro-konbinazioak eta muga-balioak barne:

fn :: test str case repeat and padding => ()
      test str case repeat and padding =
        assert equals (str to upper "Abc! 123 xyz") "ABC! 123 XYZ" "AC3: str_to_upper"
        assert equals (str to lower "Abc! 123 XYZ") "abc! 123 xyz" "AC3: str_to_lower"
        assert equals (str to upper "") "" "AC3: str_to_upper empty"

        assert equals (str repeat "ab" 3) "ababab" "AC3: str_repeat 3"
        assert equals (str repeat "ab" 1) "ab" "AC3: str_repeat 1"
        assert equals (str repeat "ab" 0) "" "AC3: str_repeat 0"
        assert equals (str repeat "ab" (0 - 5)) "" "AC3: str_repeat negative -> empty"
        assert equals (str repeat "" 100) "" "AC3: str_repeat empty string -> empty"

        t0 = sys monotonic ms
        r64k = str repeat "x" 65536
        r256k = str repeat "x" 262144
        t1 = sys monotonic ms
        r8m = str repeat "x" 8000000
        assert equals (str len r64k) 65536 "AC3: str_repeat 65536 length"
        assert equals (str len r256k) 262144 "AC3: str_repeat 262144 length"
        assert equals (str len r8m) 8000000 "AC3: RG-052 str_repeat 8000000 exact length without 1 MiB cap"
        assert true ((t1 - t0) < 200) "AC3: LIB-9 str_repeat 64k+256k in < 200 ms"

        assert equals (str pad left "7" 3 "0") "007" "AC3: str_pad_left"
        assert equals (str pad right "7" 3 "0") "700" "AC3: str_pad_right"
        assert equals (str pad left "7" 4 "") "   7" "AC3: str_pad_left empty pad_ch defaults to space"
        assert equals (str pad left "7" 4 "xyz") "xxx7" "AC3: str_pad_left uses first char of pad_ch"
        assert equals (str pad left "1234" 3 "0") "1234" "AC3: str_pad_left already wider than width"
        assert equals (str pad right "1234" 3 "0") "1234" "AC3: str_pad_right already wider than width"
        ()

09.4. Kaputaren azpian: nola dagoen eraikia str Ridgun hutsean (src/main/ridgun/lib/str.rg)

ridgun-libs-en abantaila handienetako bat C-ko kutxa beltzik ez egotea da. src/main/ridgun/lib/str.rg ireki dezakezu eta eragiketa bakoitza pattern matching, | / |. guarda-zuhaitzak eta isats-errekurtsioa (TCO) erabiliz nola inplementatuta dagoen irakurri. Ikus ditzagun bere benetako inplementazioaren funtsezko piezak:

09.4.1. Barne-inplementazioa: ASCII Classification Helpers

Ikusi nola str.rg-ek lehenik fn :: ... => ... sinadurak egituratzen dituen eta kasu bakoitza lerrokatutako ekuazioen eta isats-deien bidez ebazten duen:

module :: str

fn :: is ascii space Int  => Bool
      is ascii space code =
        code == 32 or code == 9 or code == 10 or code == 13

fn :: is ascii lower Int  => Bool
      is ascii lower code =  code >= 97 and code <= 122

fn :: is ascii upper Int  => Bool
      is ascii upper code =  code >= 65 and code <= 90

fn :: to upper code Int  => Int
      to upper code code =
        | is ascii lower code = code - 32
        | otherwise           = code

fn :: to lower code Int  => Int
      to lower code code =
        | is ascii upper code = code + 32
        | otherwise           = code

09.4.2. Barne-inplementazioa: Whitespace Trimming

Ikusi nola str.rg-ek lehenik fn :: ... => ... sinadurak egituratzen dituen eta kasu bakoitza lerrokatutako ekuazioen eta isats-deien bidez ebazten duen:

fn :: first non space idx String Int Int => Int
      first non space idx s idx len =
        | idx >= len                         = len
        | is ascii space (str char at s idx) = first non space idx s (idx + 1) len
        | otherwise                          = idx

fn :: last non space end String Int => Int
      last non space end s end =
        | end <= 0                                 = 0
        | is ascii space (str char at s (end - 1)) = last non space end s (end - 1)
        | otherwise                                = end

fn :: str trim left String => String
      str trim left s      =
        s str len -> len
        first non space idx s 0 len -> start
        str slice s start len

fn :: str trim right String => String
      str trim right s      =
        s str len -> len
        last non space end s len -> end
        str slice s 0 end

fn :: str trim slice String Int Int => String
      str trim slice s start end =
        | start >= end = ""
        | otherwise    = str slice s start end

fn :: str trim String => String
      str trim s      =
        s str len -> len
        first non space idx s 0 len -> start
        last non space end s len -> end
        str trim slice s start end

fn :: str is blank String => Bool
      str is blank s      =  s str trim -> str is empty

09.4.3. Barne-inplementazioa: String Splitting & Joining

Ikusi nola str.rg-ek lehenik fn :: ... => ... sinadurak egituratzen dituen eta kasu bakoitza lerrokatutako ekuazioen eta isats-deien bidez ebazten duen:

fn :: str split chars String Int Int [String] => [String]
      str split chars s idx slen acc =
        | idx >= slen = acc
        | otherwise   = str split chars s (idx + 1) slen (acc :: [str slice s idx (idx + 1)])

fn :: str split onech loop String Int Int Int Int [String] => [String]
      str split onech loop s d0 pos slen seg_start acc =
        | pos >= slen = acc :: [str slice s seg_start slen]
        | (str char at s pos) == d0 =
          seg = str slice s seg_start pos
          str split onech loop s d0 (pos + 1) slen (pos + 1) (acc :: [seg])
        | otherwise =
          str split onech loop s d0 (pos + 1) slen seg_start acc

fn :: str split loop String String Int Int Int Int Int [String] => [String]
      str split loop s delim d0 pos slen dlen seg_start acc =
        | pos + dlen > slen = acc :: [str slice s seg_start slen]
        | (str char at s pos) == d0 and (str slice s pos (pos + dlen)) == delim =
          seg = str slice s seg_start pos
          str split loop s delim d0 (pos + dlen) slen dlen (pos + dlen) (acc :: [seg])
        | otherwise =
          str split loop s delim d0 (pos + 1) slen dlen seg_start acc

fn :: str split step String String Int Int => [String]
      str split step s delim slen dlen =
        | dlen == 0 = str split chars s 0 slen []
        | dlen == 1 = str split onech loop s (str char at delim 0) 0 slen 0 []
        | otherwise = str split loop s delim (str char at delim 0) 0 slen dlen 0 []

fn :: str split String String => [String]
      str split s      delim  =
        str split step s delim (str len s) (str len delim)

fn :: str join pair step [String] String [String] => [String]
      str join pair step []         _   acc =  acc
      str join pair step (a:[])     _   acc =  acc :: [a]
      str join pair step (a:b:rest) sep acc =
        str join pair step rest sep (acc :: [a + sep + b])

fn :: str join pairs [String] String => String
      str join pairs []       _   =  ""
      str join pairs (x:[])   _   =  x
      str join pairs (x:y:[]) sep =  x + sep + y
      str join pairs xs       sep =
        str join pairs (str join pair step xs sep []) sep

fn :: str join [String] String => String
      str join xs       sep    =  str join pairs xs sep

09.4.4. Barne-inplementazioa: Repetition & Padding

Ikusi nola str.rg-ek lehenik fn :: ... => ... sinadurak egituratzen dituen eta kasu bakoitza lerrokatutako ekuazioen eta isats-deien bidez ebazten duen:

fn :: str repeat loop String Int String => String
      str repeat loop cur n acc =
        | n <= 0       = acc
        | (n % 2) == 1 = str repeat loop (cur + cur) (n / 2) (acc + cur)
        | otherwise    = str repeat loop (cur + cur) (n / 2) acc

fn :: str repeat String Int => String
      str repeat s      n   =
        | n <= 0 or (str len s) == 0 = ""
        | otherwise                  = str repeat loop s n ""

fn :: pad fill unit String => String
      pad fill unit pad_ch =
        | (str len pad_ch) == 0 = " "
        | otherwise             = str slice pad_ch 0 1

fn :: str pad left step String Int String Int => String
      str pad left step s width pad_ch slen =
        | slen >= width = s
        | otherwise     = (str repeat (pad fill unit pad_ch) (width - slen)) + s

fn :: str pad left String Int String => String
      str pad left s width pad_ch =
        str pad left step s width pad_ch (str len s)

fn :: str pad right step String Int String Int => String
      str pad right step s width pad_ch slen =
        | slen >= width = s
        | otherwise     = s + (str repeat (pad fill unit pad_ch) (width - slen))

fn :: str pad right String Int String => String
      str pad right s width pad_ch =
        str pad right step s width pad_ch (str len s)

09.5. Berme algoritmikoak, RMM1/RMM2 memoria eta str-en Urrezko 5 Arauak

  • Berme algoritmikoa eta segurtasunekoa: $O(\log N)$ errepikapena kateen bikoizketaren bidez, predikatu seguruak orratz hutsen aurrean eta zero mutazio bertan.
  • $O(1)$ pila-konplexutasuna TCOrekin: src/main/ridgun/lib/str.rg-eko begizta errekurtsibo guztiak isats-posizioan daude; beraz, ridgunc-ek pila-hazkuntzarik gabeko jauzi natiboetara konpilatzen ditu.
  • Memoria determinista (RMM1/RMM2): Zero zabor-biltzaile etenaldi; tarteko egitura guztiak modu deterministan askatzen dira esparrutik irtetean.
  • Etengabeko egiaztapena: Zorrotz probatua stable check eta src/test/ridgun/test str.rg suite automatizatuaren bidez.

str-ekin programatzeko Urrezko 5 Arauak

  1. Deklaratu import str fitxategiaren hasieran eta baliatu zuriuneen eta azpimarren arteko baliokidetasuna zure kodea prosa bezala irakur dadin.
  2. Lerrokatu zure datu-hodiak = ikurrarekin: kateatu str-erako deiak izen propioko urratsetan eta utzi stable format-i zutabeak lerrokatzen.
  3. Baliatu str-eko funtzio osoak zure | guardetan: egiaztatu itzulera-balioak edo askatu ADTak pattern matching bidez, kanpoko sarrera beti baliozkoa dela suposatu beharrean.
  4. Saihestu egitura handiak kopiatzea eremu bat kontsultatu besterik behar ez baduzu: gogoratu RMM2-n sarrerako argumentuek ez dituztela kontagailuak handitzen edo txikitzen (+0 / -0).
  5. Konbinatu str eta test (import test): idatzi beti asertzioak assert equals edo assert true erabiliz zure domeinuaren inbarianteak finkatzeko.

10. kapituluan math lib-a sakonki esploratuko dugu (math lib-a — Aritmetika Segurua, Zenbaki-teoria eta Estatistika).