decl sum 'a[#add] : 'a -> 'a -> 'a
def sum : a b = a + b

decl fib : \int -> \int
def fib : n =
  match n with
    | 0 | 1 -> 1
    | n ?? n > 1 -> fib: (n - 1) + fib: n
    | _ -> error: "n must be positive"

decl fact : \int -> \int
def fact : n =
  match n with
    | 0 -> 1
    | n ?? n > 0 -> n * fact: (n - 1)
    | _ -> error: "n must be positive"

decl find-prefix-hashes 'h[#acc-hash[char]] : \string -> \array['h]
def find-prefix-hashes : str = {
  var hashes = \array['h]..new: (str..size: + 1)

  ; hashes`0 = 'h..of: str`0
  for i in 1--hashes..size: do {
    ; hashes`i = hashes`(i - 1)
    ; hashes`i..append: str`i
  }

  return hashes
}

alias \hash = \acc-hash[char]

decl find-substring : ::str \string -> ::substr \string -> \array[index]
def find-substring : str substr = {
  var result = \array[index]..empty:

  let str-hashes = find-prefix-hashes:[hash] str
  let substr-hash = \hash..of: substr

  for i in 0--(str-hashes..size: - substr..size:) do {
    let part-hash = hash..diff: str-hashes`(i + substr..size:) str-hashes`i

    if part-hash == substr-hash then {
      ; result..push: i
    }
  }

  return result
}

decl is-empty : -> \bool
def is-empty = 0

decl do-something : -> \unit
def do-something =
  \io..print: "Hello World!"

decl mul : \int -> \int -> \int
def mul : x y = x * y

decl mul-10 : \int -> \int
def mul-10 = mul: 10

exec main {
  ; find-substring:
      ::str "abacaba"
      ::substr "bac"
}