[Haskell-cafe] The difficulty of designing a sequence class

[Brian Hulley]

Brian Hulley wrote:
>    class Foldable f  where
>         fold :: (a -> b -> b) -> b -> f a -> b
>         foldL :: ...
>
>    class Reduce f where -- based on FingerTree paper
>        reduceR :: (a -> b -> b) -> (f a -> b -> b)
>        reduceL :: (b -> a -> b) -> (b -> f a -> b)
>
>    class TakeDrop f where
>        take :: Int -> f a -> f a
>        takeWhile :: (a -> Bool) -> f a -> f a
>        drop ...
>
>    class Filter f where
>        filter :: (a -> Bool) -> f a -> f a
>        partition :: (a -> Bool) -> f a -> (f a, f a)
>
>    class Indexable f where
>       length :: f a -> Int
>       at :: Int -> f a -> f a -- (*)
>       splitAt :: Int -> f a -> (f a, f a)
>
[snip]
>  I personally don't have enough experience of
> Haskell yet to be able to recommend a solution.

None of the above type classes would be compatible with Data.ByteString! 
(You mentioned this issue before wrt Data.Edison.Seq but it just clicked 
with me now for the above refactoring.) For compatibility, the element type 
would need to appear also thus:

   class Foldable f_a a | f_a -> a where
        fold :: (a -> b -> b) -> b -> f_a -> b

   class Reduce f_a a | f_a -> a where
        reduceR :: (a -> b -> b) -> (f_a -> b -> b)
        reduceL :: (b -> a -> b) -> (b -> f_a -> b)

   instance Reduce [a] a where
        reduceR  f  l  x = foldr f  x  l
        -- etc

Thus Data.ByteString, as well as being extremely useful to store strings 
(!), is a central lynchpin in the entire re-factoring question since it's an 
example of a  non-polymorphic collection type (or a collection with 
restricted polymorphism), and supporting it would require a redesign of 
existing ideas in this direction eg 
http://cvs.haskell.org/Hugs/pages/libraries/base/Data-Foldable.html is no 
use either.

Regards, Brian.

-- 
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com