require 'mathn'

N = 4
f = [9,1,2,0]

Haar = Matrix[[1,1],[1,-1]]/2
R = Proc.new {|x,y| (Haar*Vector[x,y]).to_a}

def FWT(arr,s=0,n=arr.size)
  abort 'error! not powers of 2' if n%2!=0
  if n==2 then
    arr[s],arr[s+1] = R.call(arr[s],arr[s+1])
  else
    arr[s,n] = arr.slice(s,n).each_slice(2).map(&R).transpose.flatten
    FWT(arr,s,n/2)
  end
  return
end

puts f
FWT(f)
puts f