Require Import Arith List Bool.
(* Q1: Define a function that adds up the first k odd numbers,
1, 3, 2 k - 1 (the value for 0 is 0). *)
(* The following is a model of string searching in a text and decomposing
a text into lines. *)
(* Q2: Define a function headeq : list nat -> list nat -> bool, which
returns true exactly when the first list is the head of the second one. *)
(* Q3: Define a function index : list nat -> list nat -> bool, which
returns true exactly when the first list occurs in the second one;
use the previous function. *)
(* Q4: Definition a function decompose : nat -> list nat -> list (list nat)
which breaks down a list of numbers into the fragments separated
by the number given as argument. Intuition: think of the natural number
as the code for end of lines, we want to decompose a text into the
list of lines. *)
(* Q5: Define a function recompose : nat -> list (list nat) -> list nat
so that (recompose fs) is the inverse of (decompose fs) *)
(* Q6: Define a function replace : list nat -> list nat -> list nat -> list nat
which substitutes every instance of the first argument with the second
argument in the third argument. for instance
replace (2::3::nil) (7::8::nil) (1::2::3::4::5::6::nil)
should return 1::7::8::4::5::6
*)