For any non-negative infinite sequence X = {x[1], x[2], ....}, denote m[i] as the max sum of non-adjacent elements till x[i], say:

m[i] is the max-sum of {x[1], x[2], ...., x[i]} without any adjacent elements.

Specially, m[0] is max-sum of empty list, we have two trivial cases:

```
m[0] = 0, m[1] = x[1]
```

For any i > 1, we have the recursive case:

```
m[i] = max (x[i] + m[i-2]) and m[i-1]
```

This remind us the famous Fibonacci infinite definition:

```
F = 0, 1, zip(+, F, F')
```

This equation can be explained as the following table:

```
F : 0, 1, 1, 2, 3, 5 , 8 , ...
F': 1, 1, 2, 3, 5, 8 , 13, ...
zip+: 1, 2, 3, 5, 8, 13, 21, ...
```

We can do the same job with this problem. Put all m[i] together, we have an infinite list as M = {m[0], ,m[1], m[2], ....}, Removing the first m[0], denote the rest as M' = {m[1], m[2], m[3], ...}, we can draw a table like the following:

```
X: x[1], x[2], x[3], ...
M: 0, x[1], m[2], ....
M': x[1], m[2], m[3], ...
```

And here is the recursive definition of the infinite sequence M:

```
M = 0, x[1], zip(lambda(x', m, m') => max(x'+m, m'), X', M, M')
```

Translate it into Haskell, we have the following implementation:

```
maxsums [] = [0]
maxsums [x] = [0, x]
maxsums (x:xs) = ms where
ms = 0 : x : zipWith3 (\x' m m' -> max (x' + m) m') xs ms (tail ms)
```

We can easily verify the result with the imperative solution:

```
maxsum2 xs = max a b where
(a, b) = foldl (\(i, e) x -> (x + e, max i e)) (0, 0) xs
prop_maxsums :: [Int] -> Bool
prop_maxsums xs = let ns = map (abs . (`mod` 1000)) xs in maxsum2 ns == (last $ maxsums ns)
```