Re: how to write a list builder? fixpoint?
Is it possible to write a function to build a list [a]? so that I can write [a,b,c,d] as "getBuilt $ build a b c d"?
Yes, in the format very close to desired.
{-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-}
module Foo where
class BuildList a r | r-> a where build' :: [a] -> a -> r
instance BuildList a [a] where build' l x = reverse$ x:l
instance BuildList a r => BuildList a (a->r) where build' l x y = build'(x:l) y
That's it. It works both on GHC and Hugs. *Foo> build' [] True :: [Bool] [True] *Foo> build' [] True False :: [Bool] [True,False] *Foo> build' [] True False False :: [Bool] [True,False,False] *Foo> build' [] 'a' 'b' 'c' 'd' 'e' :: [Char] "abcde" *Foo> build' [] (1::Int) :: [Int] [1] *Foo> build' [] (1::Int) (2::Int) :: [Int] [1,2] *Foo> build' [] (1::Int) (2::Int) (3::Int) :: [Int] [1,2,3] Note that the type annotation [Bool] etc. at the end is required: it is the delimiter of the list. Who would have thought that the type annotation can play the role of Nil...
Thanks Oleg. This is really a nice example. Never even dream about such wonderful use of type classes! It seems to me that the "fallow-undecidable-instances" for this example is not necessary though. It compiles with just glasgow-exts Another question about overloading with type classes. It seems that these overloaded functions cannot be passed as higher-order function. Is that true?A higher order function can never be overloaded? In an example, how can I pass "build" as a function to another function that does some algorithm? (as the traditional Builder pattern in OO term) myalg builder = ...... build a b c ...... Ben. oleg@pobox.com Sent by: To: haskell@haskell.org haskell-bounces@h cc: askell.org Subject: [Haskell] Re: how to write a list builder? fixpoint? 06/01/2004 08:18 PM Please respond to oleg
Is it possible to write a function to build a list [a]? so that I can write [a,b,c,d] as "getBuilt $ build a b c d"?
Yes, in the format very close to desired.
{-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-}
module Foo where
class BuildList a r | r-> a where build' :: [a] -> a -> r
instance BuildList a [a] where build' l x = reverse$ x:l
instance BuildList a r => BuildList a (a->r) where build' l x y = build'(x:l) y
That's it. It works both on GHC and Hugs. *Foo> build' [] True :: [Bool] [True] *Foo> build' [] True False :: [Bool] [True,False] *Foo> build' [] True False False :: [Bool] [True,False,False] *Foo> build' [] 'a' 'b' 'c' 'd' 'e' :: [Char] "abcde" *Foo> build' [] (1::Int) :: [Int] [1] *Foo> build' [] (1::Int) (2::Int) :: [Int] [1,2] *Foo> build' [] (1::Int) (2::Int) (3::Int) :: [Int] [1,2,3] Note that the type annotation [Bool] etc. at the end is required: it is the delimiter of the list. Who would have thought that the type annotation can play the role of Nil... _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.
Another question about overloading with type classes. It seems that these overloaded functions cannot be passed as higher-order function. Is that true? A higher order function can never be overloaded?
In an example, how can I pass "build" as a function to another function that does some algorithm? (as the traditional Builder pattern in OO term)
A function that takes a polymorphic function and uses it polymorphically has a higher-ranked type. Higher-ranked types cannot be inferred (in general) and must be declared explicitly. In great detail, this question is discussed in Ken Shan's survey http://www.eecs.harvard.edu/~ccshan/cs252/usage.pdf As to your question: we can indeed pass 'build' to other functions and use that argument as a function with the variable number of arguments. Please see the function use_build in the code below. It works both in GHC and Hugs. P.S. Sorry I cannot reply directly to you: your ISP combined.com blocks my mail. {-# OPTIONS -fglasgow-exts #-} module Foo where class BuildList a r | r-> a where build' :: [a] -> a -> r instance BuildList a [a] where build' l x = reverse$ x:l instance BuildList a r => BuildList a (a->r) where build' l x y = build'(x:l) y --build :: forall r a. (BuildList a r) => a -> r build x = build' [] x -- build 'a' :: String -- build 'a' 'b' :: String -- build (1::Int) :: [Int] -- build (1::Int) (2::Int) :: [Int] -- build (1::Int) (2::Int) (3::Int) :: [Int] -- polyvariadic functions -- functions with the variable number of -- arguments -- are possible in Haskell after all... -- Higher-ranked type: the signature is required use_build::(forall r a. (BuildList a r) => a -> r) -> x -> x -> x -> x -> [[x]] use_build bb a b c d = let t1 = bb a t2 = bb a b t3 = bb a b c t4 = bb a b c d t5 = bb a b c d a in [t1,t2,t3,t4,t5] test = use_build build 'a' 'b' 'c' 'd' -- *Foo> test -- ["a","ab","abc","abcd","abcda"]
I'm sorry I couldn't resist another example -- which requires fewer signatures. It also illustrates storing build in data structures. In the example below (which works with the code posted earlier) build is used to build itself. It really has quite a few faces... data W = W (forall r a. (BuildList a r) => (a->r)) test2 = let t1 = build (W build) t2 = build (W build) (W build) t3 = t1 ++ t2 f (W b) = b (1::Int) ++ b (1::Int) (2::Int) ++ b (1::Int) (2::Int) (3::Int) in map f t3 We should probably move to Cafe for further discussions, if any...
I'm sorry. I'm new to haskell, new to this group, don't even know what this "cafe" refers to. Is there a special place for discussing further details? As for the build, I was really surprised by your examples. with brain adapted to Java and C++ so deeply, seems like I just cannot think well in Haskell. Each of your example made me feel :" Wow, that's cool! How come I never thought of it?". But I just cannot get everything organized in my mind. I'm ordering the "Haskell school of expression" book, hopefully it can refactor my Object Orientized brain more Haskellsih. But anyway, let's move on. Inspired by you, I wrote (most copy-paste from yours) my generic Builder which can build not only list. class Builder c a r | r -> a where build :: (c->c) -> (a -> c -> c) -> c -> a -> r instance Builder [a] a [a] where build pub acc l a = pub $ acc a l instance Builder c a r => Builder c a (a->r) where build pub acc l a x = build pub acc (acc a l) x With this generic builder, list builder can be written as: buildl :: (Builder [a] a r) => a -> r buildl = build reverse (:) [] Similarly, a builder can be built for binary functions like addToFM. class Builder2 c a b r | r -> a, r->b where build2 :: (c->c) (a->b->c->c) -> c -> a -> r instance Builder2 c a b r => Builder c a b (a->r) where build2 pub acc l a b x y = build2 pub acc (acc a b l) x y instance Builder2 (FiniteMap k v) k v (FiniteMap k v) where build2 pub acc m k v = pub $ acc k v m buildm :: (Ord k, Builder2 (FiniteMap k v) k v r) => k -> v -> r buildm = build2 id _put emptyFM where _put k v m = addToFM m k v test3 = addToFM(buildm "a" "b" "c" "d") "x" "y" I'm not bothered too much for explicitly writing the signature. It is good practice to write explicit signature anyway. However, I don't quite like having to say buildl (1::Int). If I can say [1,2,3], which types to Num a => [a], why can't I say buildl 1 2 3 which also types to Num a => [a]? oleg@pobox.com Sent by: To: haskell@haskell.org haskell-bounces@h cc: askell.org Subject: [Haskell] Re: how to write a list builder? fixpoint? 06/02/2004 07:07 PM Please respond to oleg I'm sorry I couldn't resist another example -- which requires fewer signatures. It also illustrates storing build in data structures. In the example below (which works with the code posted earlier) build is used to build itself. It really has quite a few faces... data W = W (forall r a. (BuildList a r) => (a->r)) test2 = let t1 = build (W build) t2 = build (W build) (W build) t3 = t1 ++ t2 f (W b) = b (1::Int) ++ b (1::Int) (2::Int) ++ b (1::Int) (2::Int) (3::Int) in map f t3 We should probably move to Cafe for further discussions, if any... _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.
Ben Yu wrote:
I'm new to haskell, new to this group, don't even know what this "cafe" refers to. Is there a special place for discussing further details?
Yes, http://haskell.org/mailman/listinfo/haskell-cafe
Similarly, a builder can be built for binary functions like addToFM.
Here's a bit more general variant of it:
class Builder2 c a b r | r -> a where build2 :: (a->b->c a b->c a b) -> c a b -> a -> b -> r instance Builder2 c k v (c k v) where build2 acc seed k v = acc k v seed instance Builder2 c a b r => Builder2 c a b (a->b->r) where build2 acc seed a b x y = build2 acc (acc a b seed) x y
newtype AL a b = AL [(a,b)] deriving Show
test1::AL String Bool test1 = build2 (\x y (AL l) -> AL $ (x,y):l) (AL []) "a" True "b" False
test2:: FiniteMap String Bool test2 = build2 (\x y m -> addToFM m x y) emptyFM "a" True "b" False "c" True
The function build2 not only has the variable number of arguments. These arguments don't even have to be of the same type.
However, I don't quite like having to say buildl (1::Int). If I can say [1,2,3], which types to Num a => [a], why can't I say buildl 1 2 3 which also types to Num a => [a]?
[1,2,3] is a syntactic sugar for 1:(2:(3:[])). The operator (:) has the type (:) :: forall a. a -> [a] -> [a] Since (:) is actually a function, the type of the result (which is [a]->[a]) is unambiguously determined by the type of the argument, 'a'. Informally, the type of a function has a functional dependency. The function build' is a member of a class such that the type of the result of build' unambiguously determines the type of the argument. Note the reverse implication. Therefore, once we specify the type of the result, everything works out. And it does: Foo> build 1 2 3 4 :: [Int] [1,2,3,4] In Hugs. But not in GHC (6.0.1). My impression is that GHC assumes overlapping instances when choosing instances -- even if no -fallow-overlapping-instances flag is present. In order to get the example work in GHC, we have to assure that all arguments to build have the same type in some other way, e.g., using local type variables: *Foo> let (a::t)=1 in let b=(2::t); c=(3::t) in build a b c a b c ::[t] [1,2,3,1,2,3] The result is actually polymorphic, Num t => [t].
participants (2)
-
Ben.Yu＠combined.com -
oleg＠pobox.com