Re: [Haskell-cafe] type families and type signatures
On Thu, Apr 10, 2008 at 4:20 AM, Manuel M T Chakravarty [EMAIL PROTECTED] wrote: the five signatures forall a. S a forall b. S b forall a b. S (a, b) Int S Int By alpha-convertible I mean the usual thing from lambda calculus, they are identical modulo the names of bound variables. So only the first two are alpha-convertible to each other. If you involve any kind of reduction the equivalence test is no longer trivial. All I'm asking for really, is to be able to paste in the type that was inferred as the signature, without the compiler complaining. -- Lennart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type families and type signatures
I didn't say TF was the only broken feature in GHC. But I want to see the broken ones removed, instead of new ones added. :) In the current GHC there are even definitions that are perfecty usable, that cannot be given the type signature that that was inferred. At work we have the warning for missing signatures enabled, and we turn warnings into errors. We have to disbale this for certain definitions, because you cannot give them a signature. I find that broken. -- Lennart On Thu, Apr 10, 2008 at 5:52 AM, Manuel M T Chakravarty [EMAIL PROTECTED] wrote: Lennart Augustsson: Let's look at this example from a higher level. Haskell is a language which allows you to write type signatures for functions, and even encourages you to do it. Sometimes you even have to do it. Any language feature that stops me from writing a type signature is in my opinion broken. TFs as implemented in currently implemented ghc stops me from writing type signatures. They are thus, in my opinion, broken. The problem of ambiguity is not at all restricted to TFs. In fact, you need neither TFs nor FDs to get the exact same behaviour. You don't even need MPTCs: {-# LANGUAGE FlexibleContexts #-} module Ambiguity where class C a bar :: C (a, b) = b - b bar = id bar' :: C (a, b) = b - b bar' = bar This gives us /Users/chak/Code/haskell/Ambiguity.hs:10:7: Could not deduce (C (a, b)) from the context (C (a1, b)) arising from a use of `bar' at /Users/chak/Code/haskell/Ambiguity.hs:10:7-9 Possible fix: add (C (a, b)) to the context of the type signature for `bar'' or add an instance declaration for (C (a, b)) In the expression: bar In the definition of `bar'': bar' = bar So, we have this problem as soon as we have flexible contexts and/or MPTCs, independent of TFs and FDs. Manuel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type families and type signatures
On Thu, Apr 10, 2008 at 4:20 AM, Manuel M T Chakravarty [EMAIL PROTECTED] wrote: Lennart Augustsson: On Wed, Apr 9, 2008 at 8:53 AM, Martin Sulzmann [EMAIL PROTECTED] wrote: Lennart, you said (It's also pretty easy to fix the problem.) What do you mean? Easy to fix the type checker, or easy to fix the program by inserting annotations to guide the type checker? Martin I'm referring to the situation where the type inferred by the type checker is illegal for me to put into the program. In our example we can fix this in two ways, by making foo' illegal even when it has no signature, or making foo' legal even when it has a signature. To make it illegal: If foo' has no type signature, infer a type for foo', insert this type as a signature and type check again. If this fails, foo' is illegal. That would be possible, but it means we have to do this for all bindings in a program (also all lets bindings etc). Of course, but I'd rather the compiler did it than I. It's not that hard, btw. If the whole module type checks, insert all signatures and type check again. Making it legal might be cheaper, though. -- Lennart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type families and type signatures
To make it legal: If foo' with a type signature doesn't type check, try to infer a type without a signature. If this succeeds then check that the type that was inferred is alpha-convertible to the original signature. If it is, accept foo'; the signature doesn't add any information. This harder, if not impossible. What does it mean for two signatures to be alpha-convertible? ..[type synonym expansion vs type synonym family reduction] So, I guess, you don't really mean alpha-convertible in its original syntactic sense. We should accept the definition if the inferred and the given signature are in some sense equivalent. For this equivalence to be robust, I am sure we need to define it as follows, where = is standard type subsumption: t1 equivalent t2 iff t1 = t2 and t2 = t1 i would like to express my doubts about this assumption (which relates directly to the earlier discussion about subsumption). no matter what subsumption or what semantic equivalence we are talking about, we expect it to *include* syntactic identity (reflexivity of the relations): forall t: t = t forall t: t ~ t moving some equational theory into the syntactic equivalence does not imply that syntactic has to be the full semantic equivalence - as the example of alpha- vs beta+alpha- convertibility in lambda calculus demonstrates, it is convenient to be able to ignore some representational issues when talking about identical terms in the greater theory. it would help to do the same here, and distinguish between a syntactic and a semantic equivalence of types, where the latter includes and extends the former: syntactic: alpha-conversion, permutation of contexts, probably type synonym expansion (because they are treated as syntactic macros, outside the theory) semantic: type family reduction, .. i'm tempted to the conclusion that the inability of the current system to check its inferred signatures means that reflexivity (of type subsumption/equivalence) is violated: if two types are the same, they should be equivalent and subsume each other. i can't see how the theory can work without this? However, the fact that we cannot decide type subsumption for ambiguous types is exactly what led us to the original problem. So, nothing has been won. imho, the trick is to separate syntactic and semantic equivalence, even if we include some modulo theory in the former. both = and ~ need to include this syntactic equivalence. but syntactic equivalence should remain straightforward to check - nothing should be included in it that isn't easily checkable. claus ps i hope it is obvious that i'd like infered signatures to be checkable, not non-checkable signatures to be rejected?-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] PhD or PostDoc opening in Dresden, Germany
There is a research position on offer in the project described at: http://wwwtcs.inf.tu-dresden.de/~voigt/project/ The official job advertisement (in German) can be found at: http://www.verw.tu-dresden.de/StellAus/einzelstelle.asp?id=783 The most important details are: - full-time faculty position - payment according to German public sector scale E 13 TV-L Ost (gross monthly salary expected to start around 2680 Euro) - no teaching duties - initial appointment for up to 30 months - no knowledge of German required (but English is) Please contact me directly with any further questions. Please also forward to potentially interested students. The closing date for applications is 15th May 2008. Best wishes, Janis Voigtlaender -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell library install question
Hello, I have configured, built and installed a library. When I runhaskell Setup.hs install, I noticed the message Registering unix-2.2.0.0... In what sense is it being registered? Can I query this registry information? Thanks, Vasili ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell library install question
Hello Vasili, Thursday, April 10, 2008, 6:12:45 PM, you wrote: Registering unix-2.2.0.0... In what sense is it being registered? Can I query this registry information? ghc-pkg -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fighting the monad stack, MonadIO
For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? Thanks for help, Adam ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ghc
Hi, Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! By the way there is no computer in the 4 or so networks I have online access to on which ghc is not installed, which might be a sign people like haskell here in Heidelberg/Mannheim, Germany. Best Regards, Cetin Sert ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Control.Parallel.Strategies
On Wed, Apr 9, 2008 at 11:10 PM, Justin Bailey [EMAIL PROTECTED] wrote: On Wed, Apr 9, 2008 at 3:03 PM, Sebastian Sylvan [EMAIL PROTECTED] wrote: Hmm, that's curious. I compile with ghc --make -threaded partest.hs -o par.exe, and then run it with par.exe +RTS -N2 -RTS. Am I making some silly configuration error? Are you running this on windows? Yep, that's the command line I used and I am running XP. Justin That is indeed weird. The only difference seems to be that you have hyperthreading, whereas I have dual cores. But as I mentioned, manual parallelism works (using forkIO)... -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell library install question
Thanks, Bulat. On Thu, Apr 10, 2008 at 9:18 AM, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Vasili, Thursday, April 10, 2008, 6:12:45 PM, you wrote: Registering unix-2.2.0.0... In what sense is it being registered? Can I query this registry information? ghc-pkg -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
Assuming you have ioAction :: IO x - BrowserAction x (from http://homepages.paradise.net.nz/warrickg/haskell/http/#browser) you can do: instance MonadIO BrowserAction where liftIO = ioAction Then you can derive MonadIO with GHC's newtype deriving. Alternatively, you can implement it directly on your type: instance MonadIO RBAction where liftIO = RBAction . lift . lift . ioAction This just inserts the proper number of lifts to bring the BrowserAction through your monad transformer stack, and then wraps it with your newtype constructor. On Thu, Apr 10, 2008 at 7:50 AM, Adam Smyczek [EMAIL PROTECTED] wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? Thanks for help, Adam ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Longest increasing subsequence
I'm trying to break out of my imperative mind-set by learning Haskell in small snippets. After a few successes I've hit a bit of a roadblock with one of the classic dynamic programming problems, the longest increasing subsequence: http://en.wikipedia.org/wiki/Longest_increasing_subsequence The most efficient algorithm relies on destructive updates, so a simple translation doesn't seem possible. I've been trying to think of a way of removing the need for destructive updates while keeping the efficiency, but so far without much luck. Ideally, I'd like to avoid threading the whole thing with a state monad, since then it would just be an imperative algorithm in disguise. Any suggestions would be very gratefully appreciated. Cheers, Matt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] instance Monad m = Functor m
On 9 Apr 2008, at 17:49, Henning Thielemann wrote: Additionally I see the problem, that we put more interpretation into standard symbols by convention. Programming is not only about the most general formulation of an algorithm but also about error detection. E.g. you cannot compare complex numbers in a natural way, that is x (y :: Complex Rational) is probably a programming error. However, some people might be happy if () is defined by lexicgraphic ordering. This way complex numbers can be used as keys in a Data.Map. But then accidental uses of () could no longer be detected. (Thus I voted for a different class for keys to be used in Data.Map, Data.Set et.al.) If one just needs to compare equal and unequal elements, then a hash- map is faster than a balanced tree map, and a total order is not needed. So those that want to use complex numbers as keys perhaps have not considered that possibility. And if one considers a total order () for all data types, then if that includes functions, then it may happen that two equal functions f, g satisfy f g. So it would not have the expected semantic properties. Hans ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
On Thu, Apr 10, 2008 at 9:50 AM, Adam Smyczek [EMAIL PROTECTED] wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? Adam, The following worked for me: + {-# LANGUAGE GeneralizedNewtypeDeriving #-} import Control.Monad.Trans import Control.Monad.State import Control.Monad.Error type BrowserAction = IO -- or something else which is in MondaIO data RBState = RBState newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) instance MonadIO RBAction where liftIO = RBAction . liftIO + Because everything inside the newtype wrapper already supports MondIO, you just need to call the version of liftIO underneath the newtype wrapper. Is that clear at all? -Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
On Thu, Apr 10, 2008 at 12:44 PM, Antoine Latter [EMAIL PROTECTED] wrote: {-# LANGUAGE GeneralizedNewtypeDeriving #-} import Control.Monad.Trans import Control.Monad.State import Control.Monad.Error type BrowserAction = IO -- or something else which is in MondaIO data RBState = RBState newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState, MonadIO) D'oh! Deriving MonadIO for the newtype should work, so long as BrowserAction is in the MonadIO class. -Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
On Thu, Apr 10, 2008 at 7:50 AM, Adam Smyczek [EMAIL PROTECTED] wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? In order to make a stack of monads an instance of MonadIO, you need to be able to run IO actions in the innermost monad (BrowserAction). Ideally, that monad itself would be an instance of MonadIO; maybe the authors of HTTP didn't do so because it would add a dependency on the mtl package (which defines the MonadIO class). Luckily, though, Network.Browser provides ioAction :: IO a - BrowserAction a which is exactly what you need to write the MonadIO instances yourself. -- Solution #1 -- instance MonadIO BrowserAction where liftIO = ioAction Then you can add MonadIO to the deriving clause for RBAction. -- Solution #2 -- instance MonadIO RBAction where liftIO = RBAction . lift . lift . ioAction This pulls IO actions manually through the stack of transformers. It might be better because if the HTTP package ever provided its own instance of MonadIO BrowserAction, that would conflict with #1. Hope that helps, -Judah ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc
2008/4/10 Cetin Sert [EMAIL PROTECTED]: Hi, Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! If I parse your question correctly, the answer is no, you do not need GHC installed to run the binaries, only to compile them. By the way there is no computer in the 4 or so networks I have online access to on which ghc is not installed, which might be a sign people like haskell here in Heidelberg/Mannheim, Germany. Best Regards, Cetin Sert ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc
Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! Nope! As long as they're compiled for the right architecture, GHC-produced binaries should run anywhere, whether GHC is there or not. This is true for any compiler that produces native binaries (as opposed to certain languages which require a virtual machine...) By the way there is no computer in the 4 or so networks I have online access to on which ghc is not installed, which might be a sign people like haskell here in Heidelberg/Mannheim, Germany. Cool! =) It's probably also a sign of the great work various people have done packaging GHC for various package systems. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc
On Apr 10, 2008, at 12:27 , Cetin Sert wrote: Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! ghc doesn't currently create shared objects, so no. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
Thanks a lot for all explanations! It looks like 'ioAction' is the key to the solution and if the Browser module did not provide/expose this function, no IO actions could be run inside the BrowserAction monad? If yes, is this a general concept/pattern how to hide functionality of a underlying monad, in this case hide IO entirely? Adam On Apr 10, 2008, at 11:02 AM, Judah Jacobson wrote: On Thu, Apr 10, 2008 at 7:50 AM, Adam Smyczek [EMAIL PROTECTED] wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? In order to make a stack of monads an instance of MonadIO, you need to be able to run IO actions in the innermost monad (BrowserAction). Ideally, that monad itself would be an instance of MonadIO; maybe the authors of HTTP didn't do so because it would add a dependency on the mtl package (which defines the MonadIO class). Luckily, though, Network.Browser provides ioAction :: IO a - BrowserAction a which is exactly what you need to write the MonadIO instances yourself. -- Solution #1 -- instance MonadIO BrowserAction where liftIO = ioAction Then you can add MonadIO to the deriving clause for RBAction. -- Solution #2 -- instance MonadIO RBAction where liftIO = RBAction . lift . lift . ioAction This pulls IO actions manually through the stack of transformers. It might be better because if the HTTP package ever provided its own instance of MonadIO BrowserAction, that would conflict with #1. Hope that helps, -Judah ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ghc
Cetin Sert wrote: Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! No. Well possibly yes if you use GHC api (e.g. for compiling a haskel code from your haskell application) but for common applications it is not required. Peter. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] library version problem
Hello, I doing work using Linux. The wrong version (for me) of the unix package seems to be visible. I see possibilities to use ghc-pkg to suppress the unix package that I don't want(2.3.0.0) but that seems dangerious. Details are below . What should I do? Regards, vasili When I do: ghci :m System.Posix I am getting the wrong version of the Unix package. I know this to be true because I did ghc-pkg latest unix and got unix-2.3.0.0 I want unix.2.2.0.0 because this version has changes that I made to the unix package. libHSunix-2.2.0.0.a is installed under /usr/local/lib/unix-2.2.0.0/ghc-6.8.2 I did a nm -a libHSunix-2.2.0.0.a and found symbols that I added. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc
Cetin Sert [EMAIL PROTECTED] writes: Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! Quick answer: No. GHC produces normal, standalone binaries. You may have problems with dynamic libraries, use ldd to check, or compile with -optl-static. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
On Thu, Apr 10, 2008 at 2:50 PM, Adam Smyczek [EMAIL PROTECTED] wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? I suspect BrowserAction does not implement MonadIO (lest you could just put MonadIO in the deriving clause). So, that depends on how BrowserAction is implemented. What package is Network.Browser in? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
Adam Smyczek wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? I would add instance MonadIO BrowserAction where liftIO = ioAction to hook Network.Browser into the monad transformer framework. I don't know why this instance is missing from Network.Browser. Maybe to avoid a dependency on the mtl? Anyway, with this instance, MonadIO can simply be derived for RBAction: newtype RBAction a = ... deriving (MonadIO, ...) Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fighting the monad stack, MonadIO
On Apr 10, 2008, at 12:42 PM, Luke Palmer wrote: On Thu, Apr 10, 2008 at 2:50 PM, Adam Smyczek [EMAIL PROTECTED] wrote: For a small webapi binding I try to implement a session like monad by building a stack including BrowserAction from Network.Browser module as following: newtype RBAction a = RBAction { exec :: ErrorT String (StateT RBState BrowserAction) a } deriving (Functor, Monad, MonadState RBState) I would like the RBAction to implement MonadIO as well, but fight with the liftIO function for hours now, without success. Any idea how the implementation of liftIO could look like? I suspect BrowserAction does not implement MonadIO (lest you could just put MonadIO in the deriving clause). So, that depends on how BrowserAction is implemented. What package is Network.Browser in? It's correct, BrowserAction does not implement MonadIO. This are the small things that confuse beginners like me :) Package http: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HTTP-3001.0.4 Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Longest increasing subsequence
The article mentioned in this thread addresses a similar problem: http://lambda-the-ultimate.org/classic/message8282.html The main idea is to start by expressing the straightforward, inefficient solution ,in this case something like: liss = maximumBy length . filter ascending . concat . map inits . tails (with ascending :: (Ord a) = [a] - Bool defined appropriately) Then apply a series of manipulations to it (each justified by a theorem) in order to arrive at the functional version of your favorite algorithm =) Some known names for (instances/applications of) this technique are map/fold fusion, deforestation and MapReduce. All the cool kids go bananas over it ;) -- Ariel J. Birnbaum ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Longest increasing subsequence
On Thursday 10 April 2008 01:20:49 pm Matt Amos wrote: I'm trying to break out of my imperative mind-set by learning Haskell in small snippets. After a few successes I've hit a bit of a roadblock with one of the classic dynamic programming problems, the longest increasing subsequence: http://en.wikipedia.org/wiki/Longest_increasing_subsequence The most efficient algorithm relies on destructive updates, so a simple translation doesn't seem possible. I've been trying to think of a way of removing the need for destructive updates while keeping the efficiency, but so far without much luck. Ideally, I'd like to avoid threading the whole thing with a state monad, since then it would just be an imperative algorithm in disguise. Any suggestions would be very gratefully appreciated. Memorization is a nice way to implement dynamic programming algorithms in Haskell. Basically, you arrange it so that the underlying runtime does the destructive updates for you. http://www.haskell.org/haskellwiki/Memoization Cheers, Matt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pattern match failure
I think you were having a similar problem in an earlier thread. Others have given answers, but I'll try to drive the point home further. In a pattern match like this: f a = case a of [Rule x y] - ... the pattern is *NOT* matched against each element of the list, but against the list as a whole. Say we have an expression like: let f [x] = True l = [1,2,3] in f l In the third line we attempt to match the list [1,2,3] against the pattern [x]. This cannot possibly work -- [x] can only match a list with a single element! I hope it's more clear now -- and that I answered the right question at all! There's more detail below if you're interested. {-# nitty-gritty on #-} In more detail, recall that [x] is nothing but syntactic sugar for x:[]. That is, the (:) constructor applied to x and []. [1,2,3] in turn stands for 1:2:3:[]. Pattern matching then proceeds: Match 1:2:3:[] against x:[] (:) matched - match 1 against x; 2:3:[] against [] Match 1 against x x is a variable, bind it to 1 Match 2:3:[] against [] Match failed! {-# nitty-gritty off #-} Have fun =) Jealous 'cause I never had any homework in Haskell, -- Ariel J. Birnbaum ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Longest increasing subsequence
You can translate the following algorithm (written in Maple 11), which can be made purely functional. [For the cognoscenti: attributes are implemented in-place in Maple, but that is really just an instance of the Decorator pattern which can be just as easily implemented with a functional Map]. Note that all the assignments below are really just let bindings. Jacques longestIncreasingSequence := proc(L::list) local n,i,j,G; uses GraphTheory; n := nops(L); G := Digraph(n , {seq(seq(`if`(L[i]L[j] , [i,j] , NULL ) , j = i+1..n) , i = 1..n-1)} ); map(op,LongestPathOfDAG(G),L); end proc: # LongestPathOfDAG := proc(G) local len, sources, v; uses GraphTheory; len := proc(v) option cache; local j,dep,longest; uses GraphTheory; dep := Departures(G,v); if dep = [] then setattribute(Float(1),v); else longest := max(seq(procname(j), j in dep)); setattribute(1 + longest, v, attributes(longest)); end if; end proc; sources := select(v - Arrivals(G,v)=[], Vertices(G)); [attributes(max(seq(len(v), v in sources)))]; end proc: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc
Hi Is GHC required to be installed on the target OS I compile Haskell binaries for in order for these binaries to run? I need a quick answer on that! No. You can compile binaries on one machine and move them to a similar machine without recompilation. If you want to move binaries to a different type of machine, you would need to cross compile, which is a lot more work Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe