Hi -
I've started work on an initial factoring of sequence ops into classes, and
already I've run into some major design issues which stand like a mountain
in the way of progress. The classes are below:
-- all code below standard BSD3 licence :-)
module Duma.Data.Class.Foldable
( Foldable(..)
) where
import qualified Data.List as List
class Foldable c a | c -> a where
foldR :: (a -> b -> b) -> b -> c -> b
foldL :: (b -> a -> b) -> b -> c -> b
foldL' :: (b -> a -> b) -> b -> c -> b
-- arg order from FingerTree paper
-- opposite to Edison arg order
reduceR :: (a -> b -> b) -> (c -> b -> b)
reduceR f xs y = foldR f y xs
reduceL :: (b -> a -> b) -> (b -> c -> b)
reduceL = foldL
reduceL' :: (b -> a -> b) -> (b -> c -> b)
reduceL' = foldL'
instance Foldable [a] a where
foldR = List.foldr
foldL = List.foldl
foldL' = List.foldl'
and
module Duma.Data.Class.BasicSeq
( BasicSeq(..)
) where
import Prelude hiding(map)
import Duma.Data.Class.Foldable
import qualified Data.List as List
import Control.Monad
class Foldable c a => BasicSeq c a where
empty :: c
isEmpty :: c -> Bool
atL :: c -> a
atR :: c -> a
pushL :: a -> c -> c
pushR :: c -> a -> c
viewL :: Monad m => c -> m (a, c)
viewR :: Monad m => c -> m (c, a)
-- (1) Should this be in its own class?
convert :: BasicSeq d a => c -> d
convert = foldR pushL empty
-- (2) Is this too general or not general enough?
map :: BasicSeq d b => (a -> b) -> c -> d
map f xs =
case viewL xs of
Just (x, xs') -> pushL (f x) (map f xs')
Nothing -> empty
instance BasicSeq [a] a where
empty = []
isEmpty [] = True
isEmpty _ = False
atL (x:_) = x
atR = List.last
pushL = (:)
pushR xs x = xs ++ [x]
viewL (x:xs) = return (x,xs)
viewL _ = fail "viewL"
viewR xs@(_:_) = return (List.init xs, List.last xs)
viewR _ = fail "viewR"
(Indexing ops like take, drop, length, at, split would be provided by a
third class and measurements (to access the power of finger trees and
similar structures) would be dealt with by a fourth class with analogous ops
ie takeWith, splitWith etc)
However already with just the above I have some questions about the
(convert) and (map) functions:
1) Because (convert) takes BasicSeq d a as a context, it is currently
impossible to provide an optimized version for specific combinations of
source/dest types eg if both types are the same (convert) should just be
(id). Does this mean I should put (convert) into its own class or should I
expect the compiler to be able to rewrite (foldR pushL empty) into (id) in
this situation?
2) Ditto with (map), but here there is another issue: it is at once too
general and too specific compared to the usual definitions of (map):
--Prelude - limited to lists only
map f (x:xs) = f x : map f xs
map _ [] = []
-- Functor - source and dest limited to the same type
fmap :: (a->b) -> f a -> f b
So even though fmap is constrained to only map between the same type, it is
more general than BasicSeq.map because the type doesn't need to be a
BasicSeq. However it is less general in the sense that fmap wouldn't allow
to map between two different instances of BasicSeq.
There is a general problem that when the element type needs to be specified
along with the type of the overall collection, there is no way to talk about
the functor type at the same time eg I'd like to be able to write something
like this:
class Functor f a b where
fmap :: (a->b) -> f a -> f b
instance (BasicSeq (f a) a, BasicSeq (f b) b) => Functor f a b where
fmap = map
but GHC complains that I'd need to use -fallow-undecidable-instances which
I'm reluctant to do because I don't know what the implications of such a
decision would be. Why are these instances for such a simple thing (ie just
pattern matching against the components of a type) already undecidable?
The issues above are the kind of problems I just don't know how to solve or
even how to approach, since there seem to be too many conflicting dimensions
in the design space. Any ideas?
Thanks, 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
