[Haskell-cafe] Using fundeps to resolve polymorphic types to concrete types
Hi, Is there any theoretical reason that functional dependencies can't be used to resolve a polymorphic type to a concrete type? For example: -- compile with -fglasgow-exts class DeriveType a b | a - b data A = A data B = B instance DeriveType A B simpleNarrow :: DeriveType A b = b - B simpleNarrow = id Since 'b' is uniquely determined by the fundep in DeriveType, it seems that this ought to work; ie, since the only type equation satisfying DeriveType A b is B - B, it should reduce to that before trying to fit its type against its body. The motivation is this case: data ComplexType a where SomeConstructor :: DeriveType a b = a - b - ComplexType a specialCaseFunc :: ComplexType A - B specialCaseFunc (SomeConstructor _ b) = b Essentially, if I have a data structure with two types used as fields, and one uniquely determines the other, I'd like to use these instances to avoid re-stating the implied one in the type equations, if possible. Is there some theoretical reason for this not to work, or is it just a limitation of GHC's current implementation? (Note, I'm testing with GHC 6.8.2, so it's possible this might be fixed in trunk already...) Thanks, Bryan Donlan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] carry state around ....
On Mon, Jul 28, 2008 at 08:48:23PM -0500, Galchin, Vasili wrote: what does a datatype with no constructors mean? E.g. data RSAStruct data EVP_PKEY data EVP_CIPHER data EVP_CIPHER_CTX data EVP_MD_CTX data EVP_MD data BIGNUM It's simply a datatype that can never have a value - a so-called 'phantom type'. They're useful when you need a type (eg as the argument for a ForeignPointer) but no need for an actual value. You can of course create values of these types using 'undefined', 'error' and friends, but this is perhaps not very useful most of the time :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Control.Exception.evaluate - 'correct definition' not so correct
Hi all, After some discussion on #haskell I decided to bring this issue to haskell-cafe. GHC's documentation for Control.Exception.evaluate states: evaluate :: a - IO a Forces its argument to be evaluated when the resultant IO action is executed. It can be used to order evaluation with respect to other IO operations; its semantics are given by evaluate x `seq` y== y evaluate x `catch` f == (return $! x) `catch` f evaluate x = f == (return $! x) = f Note: the first equation implies that (evaluate x) is not the same as (return $! x). A correct definition is evaluate x = (return $! x) = return However, if = is strict on its first argument, then this definition is no better than (return $! x). One might next consider: evaluate x = (return x) = (return $!) However, according to the monad laws, this is equivalent to: evaluate x = return $! x and we're back to where we started. Although GHC's implementation of IO is somewhat more relaxed about this, there is no guarentee that this will be the case in all IO implementations, or future versions of GHC, or different optimization flags, or... The best I've come up with so far is: evaluate x = newIORef (return $! x) = join . readIORef In any case, if = is to be guarenteed lazy, this ought to be documented somewhere (or is it?). Otherwise Control.Exception's docs should be updated to provide a more correct example and/or the caveat that = must not be left-strict for the example implementation to be correct. Thanks, Bryan Donlan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hi I need help for very simple question!
Taillefer, Troy (EXP) wrote: Hi there 1. First of all never forget your base case for exiting your recursion 2. you need to break up the problem like so import Char -- get the first word word :: String - String word [] = [] word ( x : x1 : xs ) | isSpace x = [] | isSpace x1 = x : [] | otherwise = x : x1 : word(xs) -- get everything but the first word rest :: String - String rest [] = [] rest ( x : x1 : xs ) | isSpace x = x1 : xs | isSpace x1 = xs | otherwise = rest(xs) intoWords :: String - [ String ] intoWords [] = [] intoWords ws = word(ws) : words( rest(ws) ) -- glue the first word and call recursively on the rest Personally, I think it's a bit clearer to use dropWhile and span: import Data.List import Data.Char mywords :: String - [String] mywords string | word == = [] | otherwise = word:mywords remain where (word, remain) = span (not . isSpace) . dropWhile isSpace $ string ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nested maybes
Martin DeMello wrote: On 2/5/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello J., Sunday, February 4, 2007, 11:46:57 PM, you wrote: exists s wmap = isJust $ find (==s) . snd = Map.lookup (sort s) wmap exists s wmap = Map.lookup (sort s) wmap == snd == find (==s) == isJust a==b = a=return.b Very nice! Didn't know about ==. Thanks to everyone else who responded too; I'm learning a lot from this thread. (==) is user-defined; that's what the last line is for :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List operation question
Eric Olander wrote: Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl: moves the first element to the end of the list shiftr :: [a] - [a] shiftr [] = [] shiftr (x:y) = y ++ [x] moves the last element to the head of the list shiftl :: [a] - [a] shiftl [] = [] shiftl x = [last x] ++ init x If you use Data.Sequence (new in 6.6, I think), these can be O(1): import qualified Data.Sequence as Seq import Data.Sequence ( (|), (|), (:), (:) ) shiftr seq = go (Seq.viewl seq) where go (EmptyL) = Seq.empty go (e : remain) = remain | e shiftl seq = go (Seq.viewr seq) where go (EmptyR) = Seq.empty go (remain : e) = e | remain Decomposing by elements like this is a bit unwieldy, but using the functions in Data.Traversable and Data.Foldable it shouldn't be too bad, depending on what you're doing. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: DevRandom
Yitzchak Gale wrote: Bryan Donlan wrote: This re-opens the device every time we need it. How about opening once, when it's first needed? Good idea. hDevRandom :: Handle {-# NOINLINE hDevRandom #-} hDevRandom = unsafePerformIO $ openFile /dev/random ReadMode hDevURandom :: Handle {-# NOINLINE hDevURandom #-} hDevURandom = unsafePerformIO $ openFile /dev/urandom ReadMode The NOINLINE guarantees that openFile is called only once. But does it guarantee that openFile is NOT called if we do not need it? We could check what the compilers actually do, but I am not sure we have a guarantee here. There's commentary in GHC/Conc.lhs that this is the case: {-# NOINLINE pendingEvents #-} {-# NOINLINE pendingDelays #-} (pendingEvents,pendingDelays) = unsafePerformIO $ do startIOManagerThread reqs - newIORef [] dels - newIORef [] return (reqs, dels) -- the first time we schedule an IO request, the service thread -- will be created (cool, huh?) I don't know if this is a documented guarentee however. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: DevRandom
Yitzchak Gale wrote: It's short, so I'll post it here. Any comments? readDev :: Storable a = FilePath - BlockingMode - IO (Maybe a) readDev dev mode = do h - openFile dev ReadMode hSetBuffering h NoBuffering alloca $ getMaybe h undefined where getMaybe :: Storable a = Handle - a - Ptr a - IO (Maybe a) getMaybe h undef ptr = do let size = sizeOf undef n - case mode of Blocking- hGetBufh ptr size NonBlocking - hGetBufNonBlocking h ptr size if n size then return Nothing else peek ptr = return . Just This re-opens the device every time we need it. How about opening once, when it's first needed? hDevRandom :: Handle {-# NOINLINE hDevRandom #-} hDevRandom = unsafePerformIO $ openFile /dev/random ReadMode hDevURandom :: Handle {-# NOINLINE hDevURandom #-} hDevURandom = unsafePerformIO $ openFile /dev/urandom ReadMode ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] are Monads with slightly stricter types in instances still Monads?
Julien Oster wrote: Hello, The type of the monadic bind function in the Monad class is Monad m = m a - (a - m b) - m b Now, would it be possible to create a monad with a slightly stricter type, like StrictMonat m = m a - (a - m a) - m a and, accepting that all steps of the computation would be bound to operate on the same type, would this be without any undesirable implications? It's possible, but it would be difficult to work with, I think. You wouldn't be able to do anything in the monad which takes any argument or returns any value other than type a, obviously, which would make things unwieldy to work with. You could define: class TypedMonadishThing m where returnS :: a - m a bindS :: m a - (a - m a) - m a But this bears little resembelance to Monad, as it's impossible to define join in it - join being a part of the fundamental theoretical structure of monads: join :: Monad m = m (m a) - m a For the sake of understanding monads better, I tried to write several custom monads which may or may not be useful. Among those were: * The Tracker Monad - tracks every result of every step of the sequential computation in a (normal, stricly typed) list inside of the monad This sounds a bit like the Writer monad... * The Goto Monad - sequential computation that allows restarts of the computation at arbitrarily set labels within it And this a bit like Cont :) But Haskell doesn't like those. Rightly so, because the bind function would have the stricter type mentioned above. [Otherwise the Tracker monad would have to store values of different types in its list and the Goto monad would encounter restarts at labels that process different types of the value than what has been computed so far. Both doesn't make sense.] The Writer monad (import Control.Monad.Writer) avoids the problem in your Tracker monad by explicitly annotating when you want to emit some output, with the tell function: tell :: (MonadWriter w m, Monoid w) = w - m () You can always add an annotation to catch the output of a function as well: watch :: (MonadWriter [r] m) = m r - m r watch m = do result - m tell [result] return result You can run a monad like this with: runWriter :: Writer w a - (a, w) And Cont (Control.Monad.Cont) avoids the problems with types by explicitly annotating the continuation with the type it expects: callCC :: (MonadCont m) = ((a - m b) - m a) - m a You could use this as in: foo = callCC $ \exitEarly - do -- complex computation when someCondition $ exitEarly result Cont's a bit tricky though, your computation is also annotated with its /final/ result, so: runCont :: Cont r a - (a - r) - r runCont . callCC :: ((a - Cont r b) - Cont r a) - (a - r) - r You could run the above foo like: runCont foo id where id is a function run on the final result of the continuation. I still have to prove wether those two monads follow the monadic laws at all, but that's part of my exercise. But let's say they follow the laws (I'm pretty sure that at least the Tracker monad does), is there anything else that would prevent the stricter typing from being legal or useful? Maybe I'm missing something simple. And would I still be able to use Haskell's do syntax? My first guess is yes, because it really just seems to translate into normal syntax. You might be able to trick the desugarer into accepting it by: import Prelude hiding (Monad(..)) but this is probably not what you want. The types of everything to the left of a - in such a do syntax would need to be the same. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Replacing [a] with (Set c a) in Monad instance.
Daniel McAllansmith wrote: Hello. Given: newtype Dist a = D {unD :: [(a,Int)]} instance Monad Dist where return x = D [(x,1)] d = f = D [(y,q*p) | (x,p) - unD d, (y,q) - unD (f x)] fail _ = D [] How would one change Dist to wrap an instance of the (Data.Edison.Set c a) typeclass so that the Monad instance could be implemented in terms of e.g. singleton, unionWith, empty, etc? I don't know about Data.Edison.Set, but if it's anything like base/Data.Set, then there's an Ord constraint on the elements, making it impossible to directly transform into a monad. However, Roberto Zunino came up with a clever way to bypass this problem with GADTS: http://article.gmane.org/gmane.comp.lang.haskell.cafe/18118 You may be able to apply this to your situation, using various Edison collections depending on which typeclasses your monad argument implements. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type infer
Marco TĂșlio Gontijo e Silva wrote: Hello, I'm trying to define a partition__ function that is like Data.Set.partition, but use State Monad: import Data.Set import Control.Monad.State partition__ f = do snapshot - get let (firsts, rest) = Set.partition f snapshot put rest return firsts When I try to infer it's type in ghci I got: $ ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Prelude :load partition.hs [1 of 1] Compiling Main ( partition.hs, interpreted ) Ok, modules loaded: Main. *Main :type partition__ partition__ :: (MonadState (Set a) t, Ord a) = (a - Bool) - t (Set a) Ok, then I add partition__ :: (MonadState (Set a) t, Ord a) = (a - Bool) - t (Set a) to the file and then: *Main :reload [1 of 1] Compiling Main ( partition.hs, interpreted ) partition.hs:4:0: Non type-variable argument in the constraint: MonadState (Set a) t (Use -fglasgow-exts to permit this) In the type signature for `partition__': partition__ :: (MonadState (Set a) t, Ord a) = (a - Bool) - t (Set a) Failed, modules loaded: none. Why do I need glasgow-exts to specify a type infered by GHCi without -fglasgow-exts? I'd imagine the check that you're using -fglasgow-exts is performed when parsing type signatures from the parser. When you allow GHC to infer the type, it's pulling that from Control.Monad.State, which was compiled with -fglasgow-exts - it's simply not checking that all the types you might infer from there are legal without -fglasgow-exts. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strings in Haskell
Neil Mitchell wrote: Hi Alexy, Now I'm reading a Haskell book which states the same. Is there a more efficient Haskell string-handling method? Which functional language is the most suitable for text processing? There are the Data.ByteString things, which are great, and have much less overhead. But remember that Haskell is lazy. If you are thinking well I have to process a 50Mb file, remember that Haskell will lazily read and process this file, which substantially reduces the memory requirements so only a small portion will ever be in memory at a time. Or you can get the best of both worlds by using Data.ByteString.Lazy :) Even with laziness, all the indirections that String causes hurts performance. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe