[Haskell-cafe] An ugly zip3 problem..
rendel at rbg.informatik.tu-darmstadt.de
Thu Mar 20 23:12:08 EDT 2008
Michael Feathers wrote:
> I'm working on something and it's looking rather ugly. essentially,
> it's an application of a low pass filer to a dataset.
I would not consider your code ugly. it can be made shorter, though.
> type Dataset = [Double]
> type FilterWindow3 = (Double,Double,Double)
> internalList :: [a] -> [a]
> internalList = tail . init
> lowPass3 :: FilterWindow3 -> Double
> lowPass3 (i, j, k) = (i + 2 * j + k) / 4.0
> filter3 :: (FilterWindow3 -> Double) -> Dataset -> Dataset
> filter3 f3 ds = [(f3 x) | x <- formWindows ds]
I would prefer this version to the list comprehension:
filter3 f3 = map f3 . formWindows
I tend to assume list comprehensions are doing something magical I have
to figure out while reading a program, so a comprehension for a simple
map looks wrong to me. read ahead for more magical list comprehensions.
> iterFilter :: (Dataset -> Dataset) -> Int -> Dataset -> Dataset
> iterFilter f n ds
> | n > 0 = iterFilter f (n - 1) (f ds)
> | otherwise = ds
You can use iterate and list indexing to iterate a function a specified
number of times.
iterFilter f n = (!! n) . iterate f
iterateN :: (a -> a) -> Int -> a
is a better type and name for this function.
> formWindows :: Dataset -> [FilterWindow3]
> formWindows ds =
> internalList $ zip3 x y z
> where c0 = [head ds]
> cn = [last ds]
> x = ds ++ cn ++ cn
> y = c0 ++ ds ++ cn
> z = c0 ++ c0 ++ ds
internalList will delete the first and last element, so why create it at
all? there is no problem with different list lengths, the result will be
as long as the shortest list.
formWindows ds = zip3 x y z where
x = tail ds ++ [last ds]
y = ds
z = head ds : ds
if you want to make clear what elements of the lists are used, you can use
z = head ds : init ds
instead. Note that definition for y clearly states that the middle
element is the original list. I would consider swapping x and z to help
me imagine a window moving over the dataset. as it is now, i have to
imagine a window with an integrated mirror to make it fit.
I don't like the definition of x, because I fear that the (last ds)
thunk will hang around and hold the whole list ds in memory, which is
unecessary because it's value only depends on the last element of said
list. I would therefore consider a different implementation using tails.
formWindows ds = [(f y z, y, x) | (x : y : z) <- tails (head ds : ds)]
where f x  = x
f _ (x : _) = x
the head corner case is taken care of by duplicating the head of ds. the
last corner case is taken care of by the call to f, which uses y as
default value if z doesn't contain another one. the list comprehension
is used here to do three different things:
* convert lists to tuples
* apply f
* throw away the last element of tails' result (pattern match
failure means "ignore this element" in list comprehensions)
headDefault :: a -> [a] -> a
is a sensible name for f.
> smooth :: Int -> Dataset -> Dataset
> smooth = iterFilter $ filter3 lowPass3
by inlining the definition above, this can be given as a four-liner now:
smooth n = (!! n) . iterate f where
f ds = [(g y z + 2 * y + x) / 4.0 | x:y:z <- tails (head ds : ds)]
g x  = x
g _ (x:_) = x
More information about the Haskell-Cafe