[Haskell-cafe] An ugly zip3 problem..

Michael Feathers mfeathers at mindspring.com
Sat Mar 22 08:45:01 EDT 2008


Thanks!  I learned a lot from that.


Michael

Tillmann Rendel wrote:
> 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
> 
> Probably
> 
>   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)
> 
> Maybe
> 
>   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
> 
> :-)
> 
>   Tillmann
> 


-- 
Now Playing: http://www.youtube.com/watch?v=SsnDdq4V8zg



More information about the Haskell-Cafe mailing list