- Haskell-Cafe - Haskell.org

existential type problem
by Andrew Pimlott 23 Oct '04

23 Oct '04

I'm having trouble using an existential type, becasue of what seem to be limitations in how I can express the type. I want values in my existential type to denote, for some monad, a monadic operation and a way to run the monad. Except, I want it mix the operation with operations in another monad, so it use a monad transformer. Specifically: data Foo = forall t. (MonadTrans t) => Foo ((Monad m, Monad (t m)) => t m a -> m a) -- run ((Monad m, Monad (t m)) => t m Int) -- op prog :: Foo -> IO Int prog (Foo run op) = run $ do lift $ putStrLn "Running prog" op ghci gives the error Could not deduce (Monad (t IO)) from the context (MonadTrans t) arising from use of `op' at try.hs:22 Hmm.... I see that my constraints did not mean what I expected. As the "Probable fix" suggests, I can add Monad (t IO) to the existential context to make this code type check, but I want it to work for all monads, not just IO. Something like data Foo = forall t. (MonadTrans t, (forall m. Monad m => Monad (t m))) => Foo ... But I haven't found anything like that. I would also welcome other approaches to this problem. Andrew

3 6

Relational Algebra post
by Brian Beckman 23 Oct '04

23 Oct '04

on my blog (http://weblogs.asp.net/brianbec <http://weblogs.asp.net/brianbec> ) , i've posted a couple of Haskell gadgets. One is a simulator for the "relational algebra" of database theory. The other is just an expansion of one of Paul Hudak's derivations of State monads.

1 0

Stream processors
by Peter Simons 22 Oct '04

22 Oct '04

Hi, I have run across the following idiom several times in the last few weeks: Some part of my program reads input from a 'Handle' and repeatedly calls a "stream processor" to incrementally compute some result, say an SHA1 hash, for example. All my stream processors can be reduced to the following interface: import Foreign ( Ptr, Word8 ) type Buffer = (Ptr Word8, Int) data StreamProc ctx a = SP { start :: IO ctx , feed :: ctx -> Buffer -> IO ctx , commit :: ctx -> IO a } I have to initialize some SP-specific context, then I can feed the data into a stateful computation as it comes in, and after receiving EOF I finalize the SP to obtain the result I wanted. The StreamProc interface works nicely for all kind of things, be it message digests, encryption, encoding, or parsers. And obviously, it's a rather generic concept. One that doesn't have to be re-invented every time ... Which leads to my question: Is there any generic module available that implements such a SP? Or something similar? I know the stream processors as described in Hughes' paper about Arrows, but those are pure stream processors -- they don't allow for I/O, which I need to handle the Ptr. Does anyone have a recommendation for me? Peter

4 11

Re: [Haskell-cafe] Re: Stream processors
by MR K P SCHUPKE 22 Oct '04

22 Oct '04

>No, my stream processors currently have the API I described My point was... using the IO library I posted which abstracts the buffer management, you can treat the IO as a simple list... so you don't need to manage the buffers as such and you can use a simple stream processor like: > process :: [a] -> [a] But of course you have to use the List class operators so that would become: process:: List l a => l a -> l a Keean.

2 1

Re: [Haskell-cafe] Re: Stream processors
by MR K P SCHUPKE 22 Oct '04

22 Oct '04

Okay, maybe I misunderstood, I thought by stream processors you meant functions of the type: process :: [a] -> [a] where both the input and the output are lazy lists (streams) I would assume if you want to have a stateful filter you need to maintain the state by using either: process :: [a] -> IO [a] process :: <state> -> [a] -> [a] process :: [a] -> ST s [a] Keean.

2 1

Re: [Haskell-cafe] Stream processors
by MR K P SCHUPKE 22 Oct '04

22 Oct '04

This is the interface I came up with (and its fairly efficient): data IList a i e = ICons i i (a i e) (IList a i e) | INil class List l e where nil :: l e null :: l e -> Bool head :: l e -> e tail :: l e -> l e (+:) :: e -> l e -> l e class List (l a i) e => ListPlus l a i e where (++:) :: a i e -> l a i e -> l a i e part :: a i e -> i -> l a i e -> l a i e Here's the instance for a normal list: instance List [] e where nil = [] null (_:_) = False null _ = True head (a:_) = a head _ = error "head: empty list" tail (_:l) = l tail _ = error "tail: empty list" a +: l = a:l Here's the instance for a list made of UArray buffers: instance (IArray a e,Ix i,Num i) => List (IList a i) e where nil = INil null INil = True null _ = False head (ICons i _ a _) = a!i head _ = error "head: empty list" tail (ICons i j a l) | i < j = ICons (i+1) j a l | otherwise = l tail _ = error "tail: empty list" a +: l = ICons 0 0 (array (0,0) [(0,a)]) l instance (IArray a e,Ix i,Num i) => ListPlus IList a i e where a ++: l | e >= s = ICons s e a l | otherwise = l where ~(s,e) = bounds a part a i l | e >= i = ICons s i a l | otherwise = l where ~(s,e) = bounds a Here's a feeder reading from a file: hGetIList :: ListPlus l UArray Int Word8 => Int -> Handle -> IO (l UArray Int Word8) hGetIList bufSize h = do mt <- newArray_ (0,bufSize-1) ioLoop mt where ioLoop mt = unsafeInterleaveIO $ do sz <- hGetArray h mt bufSize hd <- freeze mt case sz of 0 -> return nil n | n < bufSize -> do return (part hd (n-1) nil) | otherwise -> do tl <- ioLoop mt return (hd ++: tl) And here's an example consumer: wc :: List l Word8 => l Word8 -> Char -> Int -> Int -> Int -> (Int,Int,Int) wc l p i j k | p `seq` i `seq` j `seq` k `seq` False = undefined | not $ Main.null l, h <- (toEnum . fromEnum . Main.head) l, t <- Main.tail l = case isSpace h of False -> wc t h (i + 1) (j + if isSpace p then 1 else 0) k _ -> wc t h (i + 1) j (k + if h == '\n' then 1 else 0) | otherwise = (i,j,k) Keean.

2 1

Re: Top level mutable data structures problem
by MR K P SCHUPKE 21 Oct '04

21 Oct '04

A slight tangent, (and not GHC specific) so I have put this reply in the cafe. a way to get mutable data outside the IO monad occurs to me. If a file is a mutable data type outside of Haskell, we have hGetContents... which can be implemented with unsafeInterleaveIO, rather than unsafePerformIO. hGetContents lets you read a file from outside the IO Monad. The same applies to hGetChannel. What if there was a way to write in the same way? Say you write a function that reads lazily from a list ... you could then have: main :: IO () ... a <- hGetChannel channel hPutChannel (f a) -- this lazily puts the list to the channel. At the other end of the channel we have a state storage thread, which obeys commands sent over the output channel (read x, write y etc...) You can then write a function, which prepends the next instruction to the output list, and reads data from the input list hence manipulates the state. (the sequence of IO operations is preserved by the lists) Keean.

1 0

unneeded strictness
by Serge D. Mechveliani 20 Oct '04

20 Oct '04

Dear Haskellers, I am still trying to find out how to organize naturally a `lazy' printing of an accumulated data field. People advised me no-buffering and also the tilde usage. But there is some more obstackle. The `trace' is accumulated in fl1 by repeating consD, where data D = D {fl1 :: String, fl2 :: String} consD :: Char -> D -> D consD a d = d {fl1 = a:(fl1 d)} (tilde is not needed here?) The whole process computes res :: D in a certain complex recursive manner. One of the ways to use res is to print out the `trace' field: let res = (complexProcess ...) :: D in show $ fl1 res I need fl1 res to be formed `lazily'. For example, take 2 $ fl1 res may be ready (and shown) immediately, and last $ fl1 res may be ready long after. If it was [Char] istead of D, then this would be easy. Because head $ (a:) xs = a For example, head $ ('a':) $ (error "") = 'a' But is this true for consD and headD, where headD :: D -> Char headD = head . fl1 ? That is headD $ consD a res =?= a If res is not a bottom, then, yes. Right? And if res occurs, say, (error ""), then consD cannot intrude into fl1 res, and the whole expression has a value _|_. Right? So, generally, headD $ consD a res is not equivalent to a; hence the head members of fl1 res have to wait at least until it becomes clear that res is not a bottom. Right? So far, I see the two way-outs. 1. To insert the usage of the `trace' tool -- which does not look nice. 2. To have a result res :: [D] instead of D. And as soon as a new step appears, form res ++[d {fl1 = [step]}] where d = last res, fl2 also can be modified. Now, map fl1 res is the needed trace, which, I believe, would be formed `lazily'. I wonder a) whether there is a nicer solution, b) what happens if the Language treats the constructors as the homomorphisms. For example, head $ (a:) xs = a ==> head $ fl1 $ D {fl1 = (a:) fl1} = a Here (D, fl1) is a constructor, and its insertion between the functions head and (a:) preserves the above relation between them (is this called `bottom chasing' ?). Probably, this will eliminate unneeded strictness -- ? Thank you in advance for the explanations. Copy, please, the answer to mechvel(a)botik.ru ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Re: [Haskell-cafe] Re: subsequence
by MR K P SCHUPKE 20 Oct '04

20 Oct '04

Well I don't just want to give you the answer, but this code finds a subsequence in a list... This is from the HList library, and it looks for an ordered subtype ... but it also does what you want (it uses a four valued modal logic, which returns AllFalse, if list a is not a subtype (in-order) of b, (if the types are different there is no point in comparing values) or it returns SomeTrue, which has a value of either True or False depending on whether the list is an ordered sublist of values. -------------------------------------------------------------------- -- test for list a containing list b (elements of b occur in-order, but may -- be interleaved with other elements. class (HList r,HList s) => HContains' r s where hContains' :: r -> s -> Bool instance HContains' HNil HNil where hContains' _ _ = True instance HList r => HContains' (HCons a r) HNil where hContains' _ _ = True instance HList r => HContains' HNil (HCons a r) where hContains' _ _ = False instance (HContains' r (HCons a s),HContains' r s,Eq a) => HContains' (HCons a r) (HCons a s) where hContains' (HCons a r) s@(HCons a' s') = if a == a' then hContains' r s' else hContains' r s instance HContains' r (HCons b s) => HContains' (HCons a r) (HCons b s) where hContains' (HCons _ r) s = hContains' r s class (HList r,HList s,Logic.MBool t) => HContains'' r s t | r s -> t where hContains'' :: r -> s -> t instance HContains'' HNil HNil Logic.AllTrue where hContains'' _ _ = Logic.AllTrue instance HList r => HContains'' (HCons a r) HNil Logic.AllTrue where hContains'' _ _ = Logic.AllTrue instance HList r => HContains'' HNil (HCons a r) Logic.AllFalse where hContains'' _ _ = Logic.AllFalse instance HContains'' r s t => HContains'' (HCons a r) (HCons a s) t where hContains'' (_ :: HCons a r) (_ :: HCons b s) = hContains'' (undefined :: r) (undefined :: s) instance HContains'' r s t => HContains'' (HCons a r) s t where hContains'' (_ :: HCons a r) s = hContains'' (undefined :: r) s class (HContains' r s,Logic.Modal t) => HContains r s t | r s -> t where hContains :: r -> s -> t instance HContains' r HNil => HContains r HNil Logic.AllTrue where hContains _ _ = Logic.AllTrue instance (HContains'' r (HCons b s) t',Logic.And t' Logic.SomeTrue t,HContains' r (HCons b s)) => HContains r (HCons b s) t where hContains r s = hContains'' r s `Logic.and` Logic.toSomeTrue (hContains' r s) ---------------------------------------------------------------------------- Keean.

1 0

STG questions
by Andrew Harris 20 Oct '04

20 Oct '04

Hi - I am reading Simon Peyton Jones's "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine" (I have version 2.5) paper. I would like very much to understand the contents of Figure 5 which illustrate the mapping of the "map" function from STG code to C. However I have some questions. For example, * It looks like map_closure is the "closure" in that it has an array of StgWords and the first word is a pointer to an info table. This info table contains map_entry as the entry code. I am curious about the relationship between map_entry and map_direct. Why isn't the stuff in map_direct done in map_entry? * The ret_vec1 is a continuation that's placed on the B stack. I am assuming this is a "non-vectored" return that has contents similar to Figure 7 (which is for vectored returns), but is this true? Also, the "upd_nil" and "upd_cons" functions aren't defined in the example. Maybe they just don't do anything? * In the return_cons1() function, how did the head and tail get put into the RegData1 and RegData2 registers? * I may have missed it, but it looks like the fy and mfy use three contiguous words of heap each. Can I assume that the triple {Hp[-5], Hp[-4], Hp[-3]} are of a structure similar to figure 4, the "Layout of a closure", which in this case would have some pointer/non-pointer words? thanks for any help, -andrew

1 0