let rec haar ?(s=[]) ?(d=[]) l = match l, s with
  | ([] | [_] as s), [] -> s @ d
  | [], s -> haar ~s:[] ~d s
  | h1::h2::t, s -> haar ~s:(h1+h2::s) ~d:(h1-h2::d) t
  | _ -> invalid_arg "haar";;

haar [];;
haar [1];;
haar [1; 2];;
haar [1; 2; -1; -2];;