[Haskell-cafe] Re: Problematic irrefutable pattern matching of existentials
On Sun, Oct 01, 2006 at 08:05:15PM -0700, [EMAIL PROTECTED] wrote: > I have come to realize that irrefutable pattern matching of > existentials may indeed be problematic. Let us consider the following > existential data type > > > data FE = forall a. Typeable a => Foo a > > | forall a. Typeable a => Bar a > > The following tests type and run (the latter raising the expected > exception). > > > test1 = case (Foo ()) of Foo x -> show $ typeOf x > > test2 = case (Bar True) of Foo x -> show $ typeOf x > > Let us suppose that irrefutable pattern matching of existentials is > allowed. What would be the value of the expression > > case (Bar True) of ~(Foo x) -> show $ typeOf x > then? > > Hopefully not "Bool". One might say that the expression ought to bottom > out. However, what reason one may give for that outcome? The only > binding in the above expression is of 'x', whose value is never > demanded. Indeed, "show $ typeOf (undefined :: ())" yields the > non-bottom value "()". There is also the implicit dictionary argument of typeOf, and this is demanded, so the value should be _|_. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Problematic irrefutable pattern matching of existentials
I have come to realize that irrefutable pattern matching of existentials may indeed be problematic. Let us consider the following existential data type > data FE = forall a. Typeable a => Foo a > | forall a. Typeable a => Bar a The following tests type and run (the latter raising the expected exception). > test1 = case (Foo ()) of Foo x -> show $ typeOf x > test2 = case (Bar True) of Foo x -> show $ typeOf x Let us suppose that irrefutable pattern matching of existentials is allowed. What would be the value of the expression case (Bar True) of ~(Foo x) -> show $ typeOf x then? Hopefully not "Bool". One might say that the expression ought to bottom out. However, what reason one may give for that outcome? The only binding in the above expression is of 'x', whose value is never demanded. Indeed, "show $ typeOf (undefined :: ())" yields the non-bottom value "()". One may claim that the existential pattern match also binds an implicit dictionary argument, which is demanded above. That explanation is quite unsatisfactory, because it breaks the abstraction of type classes. The dictionary passing is merely an _implementation technique_ for type classes. Furthermore, it is not the only implementation technique: JHC and Chameleon, for example, use intensional type analysis to implement typeclasses. On a different note, Conor McBride wrote: > It isn't necessary to perform > constructor discrimination when it's statically known that exactly one > constructor is possible, so those patterns can always be made > irrefutable, with matching replaced by projection. that is, in essence, the idea behind `Tagless Staged Interpreters for Typed Languages' Pasalic, Taha, Sheard: ICFP02 It is well-written paper, with an excellent introduction and motivation. Incidentally, one can write their tagless staged interpreter in Haskell as it is. No dependent types are necessary. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: How would you replace a field in a CSV file?
[EMAIL PROTECTED] writes: > For such a small self-contained task, I don't think Haskell > is any better than Python. I figured as much, but I thought with the new FPS lazy bytestrings it might have a chance in terms of raw speed. On the other side of the coin, in terms of elegance, I thought I'd ask as haskellers always amaze me with their one-liners :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] non lazy io
Hi, I would like a non-lazy alternative to readFile is there such a thing in the libraries? Not as far as I know, but you can achieve something similar by doing: -- untested readFile' file = do src <- readFile file return $ seq (length src) src What is the particular reason you want a strict readFile for? Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] non lazy io
I would like a non-lazy alternative to readFile is there such a thing in the libraries? matt r ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How would you replace a field in a CSV file?
Hi Pete. For such a small self-contained task, I don't think Haskell is any better than Python. Haskell would come into its own if you wanted some assurance about type safety, and/or were taking on a task large enough to warrant the use of records (and hence record update notation). Regards, Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] OOHaskell problems
Hello, I wanted to try using OOHaskell as a library, but I've run into some problems I don't understand. I downloaded the copy from: http://homepages.cwi.nl/~ralf/OOHaskell/ In the HList subdirectory I created a .cabal file which exposes as many of the modules in HList as I could. I then installed the HList library using cabal. Back in the main OOHaskell directory I created a .cabal file for OOHaskell which depended on the newly installed HList library. The OOHaskell library exposes the modules: DeepNarrow New Nominal OOHaskell After I installed the OOHaskell library I ran: ghc --make -package OOHaskell -package HList SimpleIO.hs Chasing modules from: SimpleIO.hs Compiling Nominal ( ./Nominal.hs, ./Nominal.o ) Compiling New ( ./New.hs, ./New.o ) Compiling DeepNarrow ( ./DeepNarrow.hs, ./DeepNarrow.o ) Compiling OOHaskell( ./OOHaskell.hs, ./OOHaskell.o ) Compiling SimpleIO ( SimpleIO.hs, SimpleIO.o ) SimpleIO.hs:44:11: No instance for (HasField (Proxy Field1) HNil v) arising from use of `foo' at SimpleIO.hs:44:11-13 Probable fix: add an instance declaration for (HasField (Proxy Field1) HNil v) In the definition of `testfoo': testfoo = foo ((field1 .=. True) .*. emptyRecord) SimpleIO.hs:116:7: No instance for (HasField (Proxy MoveX) HNil (a -> IO t)) arising from use of `#' at SimpleIO.hs:116:7 Probable fix: add an instance declaration for (HasField (Proxy MoveX) HNil (a -> IO t)) In the first argument of `($)', namely `p # moveX' In a 'do' expression: (p # moveX) $ 3 In the definition of `myFirstOOP': myFirstOOP = do p <- point (p # getX) >>= System.IO.print (p # moveX) $ 3 (p # getX) >>= System.IO.print SimpleIO.hs:124:19: No instance for (HasField (Proxy MutableX) HNil (IORef a)) arising from use of `#' at SimpleIO.hs:124:19 Probable fix: add an instance declaration for (HasField (Proxy MutableX) HNil (IORef a)) In the first argument of `writeIORef', namely `(p # mutableX)' In a 'do' expression: writeIORef (p # mutableX) 42 In the definition of `mySecondOOP': mySecondOOP = do p <- point writeIORef (p # mutableX) 42 (p # getX) >>= System.IO.print SimpleIO.hs:177:23: No instance for (HasField (Proxy GetX) HNil (IO a)) arising from use of `#' at SimpleIO.hs:177:23 Probable fix: add an instance declaration for (HasField (Proxy GetX) HNil (IO a)) In the second argument of `(>>=)', namely `(# getX)' In the first argument of `(>>=)', namely `localClass >>= ((# getX))' In the result of a 'do' expression: (localClass >>= ((# getX))) >>= System.IO.print SimpleIO.hs:225:8: No instance for (HasField (Proxy GetOffset) HNil (IO a)) arising from use of `#' at SimpleIO.hs:225:8 Probable fix: add an instance declaration for (HasField (Proxy GetOffset) HNil (IO a)) In the first argument of `(>>=)', namely `p # getOffset' In the result of a 'do' expression: (p # getOffset) >>= System.IO.print In the definition of `testPara': testPara = do p <- para_point 1 (p # getX) >>= System.IO.print (p # moveX) $ 2 (p # getX) >>= System.IO.print (p # getOffset) >>= System.IO.print To investigate this further, in the OOHaskell directory I typed: $ ghci -fglasgow-exts -fallow-overlapping-instances -fallow-undecidable-instances -i./HList ShapesLub.hs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Compiling FakePrelude ( ./HList/FakePrelude.hs, interpreted ) Compiling HListPrelude ( ./HList/HListPrelude.hs, interpreted ) Compiling GhcExperiments ( ./HList/GhcExperiments.hs, interpreted ) Compiling HArray ( ./HList/HArray.hs, interpreted ) Compiling HZip ( ./HList/HZip.hs, interpreted ) Compiling HOccurs ( ./HList/HOccurs.hs, interpreted ) Compiling HTypeIndexed ( ./HList/HTypeIndexed.hs, interpreted ) Compiling Record ( ./HList/Record.hs, interpreted ) Compiling GhcRecord( ./HList/GhcRecord.hs, interpreted ) Compiling Label4 ( ./HList/Label4.hs, interpreted ) Compiling New ( ./New.hs, interpreted ) Compiling TIP ( ./HList/TIP.hs, interpreted ) Compiling TIC ( ./HList/TIC.hs, interpreted ) Compiling GhcSyntax( ./HList/GhcSyntax.hs, interpreted ) Compiling TypeCastGeneric1 ( ./HList/TypeCastGeneric1.hs, interpreted ) Compiling TypeEqBoolGeneric ( ./HList/TypeEqBoolGeneric.hs, interpreted ) Compiling TypeEqGeneric1 ( ./HList/TypeEqGeneric1.hs, interpreted
[Haskell-cafe] question - which monad to use?
Hi,
I have a computation where a function is always applied to the
previous result. However, this function may not return a value (it
involves finding a root numerically, and there may be no zero on the
interval). The whole problem has a parameter c0, and the function is
also parametrized by the number of steps that have been taken
previously.
To make things concrete,
type Failmessage = Int -- this might be something more complex
data Result a = Root a | Failure Failmessage -- guess I could use Either too
f :: Double -> Int -> Double 0 -> Result Double
f c0 0 _ = c0
f c0 j x = {- computation using x, parameters calculated from c0 and j -}
Then
c1 = f c0 0 c0
c2 = f c0 1 c1
c3 = f c0 2 c2
...
up to cn.
I would like to
1) stop the computation when a Failure occurs, and store that failure
2) keep track of intermediate results up to the point of failure, ie
have a list [c1,c2,c3,...] at the end, which would go to cn in the
ideal case of no failure.
I think that a monad would be the cleanest way to do this. I think I
could try writing one (it would be a good exercise, I haven't written
a monad before). I would like to know if there is a predefined one
which would work.
Thank you,
Tamas
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How would you replace a field in a CSV file?
The other day at work an opportunity arose where I was hoping to sneak
some Haskell into the pipeline of tools used to process call detail
records (CDRs). In the telecommunications industry, CDRs are used for
billing. Each CDR is a single line record of 30 comma-separated
values. Each line is approximately 240 characters in length. The
task at hand is to replace field number 10 if a new value can be found
in a hashmap which is keyed using the contents of the field.
My colleague was going to write a C program (that's all he knows), but
I whipped up a trivial python program instead. I was curious if a
haskell version could be faster and more elegant , but I have not been
able to beat my python version in either case. So, I'm curious as to
how you would go about this task in Haskell. The input files are
generally 300-400MB, and the hashmap will contain perhaps 20-30 items.
For those that know python, here is a very simple implementation that
happens to be very fast compared to my Haskell version and very short:
for line in sys.stdin:
fields = line.split(',')
fields[9] = tgmap.get(fields[9], fields[9])
print ",".join(fields),
For each line in standard input:
- Splits the string on the comma: "field0,field1,...,field29" =>
["field0", "field1", ..., "field29"] to obtain a list of strings.
- Gets the value associated with the key of field9 from tgmap, if it
does not exist, it returns a default value which is the original
value. I.e., if it's not in the map, then don't replace the
field.
- Joins the list of fields with a comma to yield a string again
which is printed out to standard output. The join method on the
string is a bit odd: ",".join([1,2,3]) => "1,2,3"
Here is my first Haskell attempt:
import Data.ByteString.Lazy.Char8 as B hiding (map,foldr)
import Data.List (map)
import Data.Map as M hiding (map)
-- This is just a placeholder until I actually populate the map
tgmap = M.singleton (B.pack "Pete") (B.pack "Kazmier")
main = B.interact $ B.unlines . map doline . B.lines
where doline= B.join comma . mapIndex fixup . B.split ','
fixup i s = if i==9 then M.findWithDefault s s tgmap else s
comma = B.pack ","
-- f is supplied the index of the current element being processed
mapIndex f xs = m f 0 xs
where m f i [] = []
m f i (x:xs') = f i x : m f (i+1) xs'
After talking with dons on #haskell, he cleaned my version up and
produced this version which gets rid of 'if' statement and makes
mapIndex stricter:
import Data.ByteString.Lazy.Char8 as B hiding (map,foldr)
import Data.List (map)
import Data.Map as M hiding (map)
-- This will be populated from a file
dict = M.singleton (B.pack "Pete") (B.pack "Kazmier")
main = B.interact $ B.unlines . map doline . B.lines
where doline= B.join comma . mapIndex fixup . B.split ','
comma = B.singleton ','
fixup 3 s = M.findWithDefault s s dict
fixup n s = s
-- f is supplied the index of the current element being processed
mapIndex :: (Int -> ByteString -> ByteString) -> [ByteString] ->
[ByteString]
mapIndex f xs = m xs 0
where m [] _ = []
m (x:xs') i = f i x : (m xs' $! i+1)
That helped things a bit, but I must confess I don't understand how
the strictness improved things as I had assumed things were going to
be evaluated in a reasonable amount of time due to the printing of
output. I thought IO was interlaced with the execution and thus I
wasn't going to have to concern myself over laziness. In addition,
the function is able to generate new elements of the list on demand so
I thought it was a good citizen in the lazy world. Could anyone help
explain?
And then he came up with another version to avoid the 'unlines', but
that did not that really speed things up significantly. So, with all
that said, is there a better approach to this problem? Perhaps a more
elegant Haskell solution?
Thanks,
Pete
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Offtopic] Re: Re: A better syntax for qualified operators?
Cale Gibbard wrote: >> "What a beautiful world this could be..." ;-)) (*) >> >> Cheers, >> Ben >> (*) Donald Fagen (forgot the name of the song) > > I think I.G.Y. (International Geophysical Year) is it: > > On that train all graphite and glitter > Undersea by rail > Ninety minutes from New York to Paris > (More leisure time for artists everywhere) > A just machine to make big decisions > Programmed by fellows with compassion and vision > We'll be clean when their work is done > We'll be eternally free yes and eternally young > > What a beautiful world this will be > What a glorious time to be free Many thanks for digging it out. Hey, it fits some of the discussions on this list even better than I remembered ;-) Cheers, Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: irrefutable patterns for existential types / GADTs
> Thanks for asking!
> [...]
> Online algorithms do look like a good place to try to get some leverage
> from this, but we haven't really been in a position to experiment so
> far. I'm sure that will change.
Well, I asked because laziness with memoization gives a definite edge in
terms of algorithmic time complexity over strictness (proved for online
algorithms in "more haste, less speed") and I wonder how this goes
together with totality and dependent types. A forthcoming ultimate
programming language should retain this edge, shouldn't it? ;-)
> It isn't necessary to perform
> constructor discrimination when it's statically known that exactly one
> constructor is possible, so those patterns can always be made
> irrefutable, with matching replaced by projection.
Thanks for pinpointing the culprit, because translated to GADTs, it
means that
"whenever we know from the type index that only one constructor is
possible, it can be made irrefutable."
So this is the kind of irrefutable pattern one could safely add. In
particular, this can be weakened to
"whenever we know the type index, i.e. there is no type refinement
depending on the value, an irrefutable pattern is safe."
But once no type refinement happens, the irrefutable pattern can already
be obtained via let bindings in existing Haskell! Below is a lazy
version of Bertram solution to the "Optimization problem" following
Ross' suggestions with existentials and GADTs:
> {-# OPTIONS_GHC -fglasgow-exts #-}
>
> data Map s k a where
> Leaf :: Map () k a
> Node :: k -> a -> Map s k a -> Map t k a -> Map (s,t) k a
(Map s k a) is a tree which makes its structure explicit in the type
index s.
>
> unNode :: Map (s,t) k a -> (k,a,Map s k a, Map t k a)
> unNode (Node k a l r) = (k,a,l,r)
unNode knows the type index and is to be used for a lazy pattern match
let (k,a,l,r) = unNode ..
> empty :: Map () k a
> empty = Leaf
>
> member :: Ord k => k -> Map s k a -> Bool
> member _ Leaf= False
> member k (Node k' _ l r) = case compare k k' of
> LT -> member k l
> EQ -> True
> GT -> member k r
>
> data Undoer s k a where
> Undoer :: (Map t k a) -> (Map t k a -> (a,Map s k a)) -> Undoer s k a
Undoer is just (exists t. ...) wrapped into a digestible type.
> -- insert key element blueprint map (blueprint, result, map)
> insert :: Ord k => k -> a -> Map s k a -> Undoer s k a
> insert k a Leaf = Undoer (Node k a Leaf Leaf)
> (\map -> let (_,a,_,_) = unNode map in (a,Leaf))
Note how the type system proves that the function (\map -> ..) always
has to expect (map) == Node ...
Then, unNode binds k',b',... /lazily/.
Same goes for the rest of insert:
> insert k a (Node k' b (l :: Map l k a) (r :: Map r k a) :: Map s k a)
> = case compare k k' of
> LT -> case insert k a l of
> Undoer (m :: Map t k a) f ->
> Undoer (Node k' b m r :: Map (t,r) k a)
> (\map -> let
> (k',b',m',r') = unNode map
> (a,l') = f m'
> in (a,Node k' b' l' r' :: Map s k a))
> EQ -> error "inserting existing element"
> GT -> case insert k a r of
> Undoer (m :: Map t k a) f ->
> Undoer (Node k' b l m :: Map (l,t) k a)
> (\map -> let
> (k',b',l',m') = unNode map
> (a,r') = f m'
> in (a,Node k' b' l' r' :: Map s k a))
>
> -- update k fun blueprint map
> update :: Ord k => k -> (a -> a) -> Map s k a -> Map s k a -> Map s k a
> update k f (Node k' _ l' r') map = case compare k k' of
> LT -> Node k' a (update k f l' l) r
> EQ -> Node k' (f a) l r
> GT -> Node k' a l (update k f r' r)
> where
> (_,a,l,r) = unNode map
Again a lazy pattern match on (map). Note that the type system enforces
that blueprint and actual (map) have the same shape s. The type
refinement for GADTs happens in the strict pattern match on the
blueprint and this allows us to lazily match the (map).
> splitSeq :: Ord a => [(a,b)] -> [(a,[b])]
> splitSeq = fst . splitSeq' empty
>
> splitSeq' :: Ord a => Map s a [b] -> [(a,b)] -> ([(a,[b])], Map s a [b])
> splitSeq' bp [] = ([], bp)
> splitSeq' bp ((a,b):xs) = case member a bp of
> True -> let (l, m) = splitSeq' bp xs in (l, update a (b:) bp m)
> _-> case insert a [] bp of
> Undoer bp' f -> let
> (rs,m) = splitSeq' bp' xs
> (bs,m') = f m
> in ((a, b:bs) : rs, m')
To summarize, the problem can be solved without irrefutable patterns for
GADTs: the code above works for infinite lists. Yet, they are handy and
can be introduced safely in the case where the type indices are known in
advance and no type refinement happens.
Regards,
apfelmus
___
Haskell-Cafe mailing list
Haskell-Ca
[Haskell-cafe] Re: Why is type 'b' forced to be type 'm a' and not possibly 'm a -> m a'
Vivian McPhail wrote: ... > I need the arg a to be evaluated before it gets > passed to a1 and a2. This definition does the right thing > when type 'a' is a function type, because it is not a > value, but with something like 'm a -> (m a -> m a) -> m > a' with Forkable (a -> b) the first arg gets evaluated > twice, to be more concrete: > > With > > (and golden white) eggs > > I want the 'eggs' that is passed to 'golden' to be the > same as the 'eggs' that is passed to 'white', i.e. ... Could you reduce the need for Forkable instances, by rewriting '(and golden white) eggs' as 'and golden white =<< eggs'? Or would the same piece of code also have to handle combinations such as monadic 'and golden white' and non-monadic eggs? [BTW, thanks for giving me a pretext to use the phrase non-monadic eggs!] > Tom suggested that I might be able to use the Reader monad > , but I'm not clear as to how I could do this. Please ignore that. I only mentioned it in case the sole purpose of fork was to propagate a String, which you've now explained is not so. Regards, Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Greetings...
Seth Gordon wrote: > I thought I should check and see if anyone > on this list has used Haskell to munge a > ten-million-row database table, and if > there are any particular gotchas I should > watch out for. Are you sure you want to target the data directly? Another approach, that might have a better chance of a quick win within your time frame, is to use Haskell to generate SQL code. That could still reduce the amount of code you maintain by hand. Regards, Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Greetings
On 10/1/06, Seth Gordon <[EMAIL PROTECTED]> wrote: Paul Johnson wrote: > I've done some stuff with maybe 50k rows at a time. A few bits and pieces: > > 1: I've used HSQL > (http://sourceforge.net/project/showfiles.php?group_id=65248) to talk to > ODBC databases. Works fine, but possibly a bit slowly. I'm not sure > where the delay is: it might just be the network I was running it over. > One gotcha: the field function takes a field name, but its not random > access. Access the fields in query order or it crashes. Thanks; that's certainly the sort of thing I like knowing in advance. This behaviour depends on the underlying database. I remember that MSSQL suffers from this disease. In addition with MSSQL you can't have more than one opened dataset for a given connection. MySQL and PostgreSQL doesn't have this problem. HSQL can't hide all differences between the possible backends. > 2: For large data sets laziness is your friend. When reading files > "getContents" presents an entire file as a list, but its really > evaluated lazily. This is implemented using unsafeInterleaveIO. I've > never used this, but in theory you should be able to set up a query that > returns the entire database as a list and then step through it using > lazy evaluation in the same way. I assume that the collectRows function in HSQL can produce this kind of a lazy list...right? No. collectRows collects all records eagerly. The problem with the lazy fetching is that you can close the database connection while your lazy data sets aren't fetched yet. It is getting worse if you can't have multiple opened data sets. If you still want lazy fetching you can write a custom function like collectRows but using unsafeInterleaveIO. Cheers, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Greetings...
On 10/1/06, Seth Gordon <[EMAIL PROTECTED]> wrote: I'm planning to use HSQL, since it's in Debian stable and the API resembles what I'm already familiar with. Database access is slower than file access (which is one reason I want to move as much logic as I can out of SQL), so if the speed of getting rows out of the database turns out to be the bottleneck in my code, I'll either be happy that all the other code is so efficient or peeved that HSQL is so inefficient. Hi Seth, HSQL is just a thin wrapper around the underlying database engine. The performance in this case depends mainly on the database engine that you are using. Cheers, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
