- Haskell-Cafe - Haskell.org

efficiency
by Feuer 16 Jan '02

16 Jan '02

In http://www.cs.columbia.edu/~cdo/icfp99.ps Okasaki does a couple things I'm not sure I quite understand: He has a datatype newtype Empty a = E () I cannot for the life of me figure out why he didn't just do data Empty a = E The other weird thing was: newtype Pair v w a = P (v a, w a) I can't see why he didn't do data Pair v w a = P (v a) (w a) I was wondering if anyone on this list knew of any reasons the types he chose would be more efficient than mine.... David

4 4

Re: efficiency
by Mike Gunter 16 Jan '02

16 Jan '02

> By the way, I don't understand why Haskell98 provides both strictness flags > and newtype declarations.... it seems to me that > newtype M [a1 a2 ....] = MC (...) > should be exactly the same as > data N [b1 b2 ....] = NC !(...) The Haskell report (in the "Datatype Renamings" section, 4.2.3, -- the one on newtype) explains the difference. Translating some of the examples there to your names, with > newtype M = M Int > m (M i) = 42 > data N = N !Int > n (N i) = 42 we get Main> m undefined 42 but Main> n undefined *** Exception: Prelude.undefined mike

2 1

Re: efficiency
by Ashley Yakeley 15 Jan '02

15 Jan '02

At 2002-01-15 00:00, Ketil's local user wrote: >When recently reading the GHC docs, the chapter about profiling, I >think, I came across something about this. From Chapter 6: > >| Newtypes are better than datatypes: >| >| If your datatype has a single constructor with a single field, >| use a newtype declaration instead of a data declaration. The newtype >| will be optimised away in most cases Does that help? data (,) a b = (,) a b; newtype Pair v w a = P (v a, w a); vs. data Pair v w a = P (v a) (w a); and data () = (); newtype Empty a = E (); vs. data Empty a = E; -- Ashley Yakeley, Seattle WA

1 0

A question from a newbie
by Chen-Chieh Feng 15 Jan '02

15 Jan '02

hi, I just started to write a few lines using hugs98. I ran into a program error that reads like this: Program error: {instDirectPositions_v1683_v1697 dir_pt} Could anybody give me a direction on how to read this error message and the possible cause of this error? Thank you very much. Chen-Chieh

2 1

RE: Help using a state monad
by Chris Angus 14 Jan '02

14 Jan '02

your pattern match of (s:sx) seems to be the cause of the delay try --Process the input mProcess :: String -> State String mProcess sx = do b <- isOn if ( head sx == 't' ) then toggle else return () appOut (tuUpper b (head sx)) (mProcess (tail sx)) instead -----Original Message----- From: Tom Bevan [mailto:tom@regex.com.au] Sent: 14 January 2002 05:58 To: Haskell Cafe List Subject: Help using a state monad Hi all, I'm trying to get a feel for how monads might be used in a Haskell program and develop an approach that would be useful for larger projects. I have tried to model in miniture a programme which takes input from 'standard in' and processes it against an internal state and then returns the processed result to 'standard out'. My problem is that, becuase of the way I have constructed the programme 'standard out' lags behind by one character. I'm hoping that someone might have a better design they could share with me. Tom.

1 0

Re: differentiation. Reply
by Jerzy Karczmarczuk 14 Jan '02

14 Jan '02

Ketil Z Malde adds a comment concerning the query of Zhe Fu: > > >>> Is there any built-in functions in Haskell to implement > >>> diffential operation and partial diffential operation? > >>> Or can anyone give me some advices about how to implement them > >>> with Haskell? Thanks. > Jerzy Karczmarczuk has some interesting papers on his web site using a > different approach to differentiation, maintaining, IIRC, a lazy list > of all derivatives of functions. I don't have the URL ready, but a > your favorite search engine should be able to help you out. === 1. First, I suggest to move this to Haskell-café. I leave the original address, though. 2. My work is about the "Automatic Differentiation" in Haskell. The paper http://users.info.unicaen.fr/~karczma/arpap/diffalg.pdf has been published in HOSC last year. But somebody might get interested in some geometric extensions thereof (differential forms) http://users.info.unicaen.fr/~karczma/arpap/ltforms.pdf Jerzy Karczmarczuk

1 0

Help using a state monad
by Tom Bevan 14 Jan '02

14 Jan '02

Hi all, I'm trying to get a feel for how monads might be used in a Haskell program and develop an approach that would be useful for larger projects. I have tried to model in miniture a programme which takes input from 'standard in' and processes it against an internal state and then returns the processed result to 'standard out'. My problem is that, becuase of the way I have constructed the programme 'standard out' lags behind by one character. I'm hoping that someone might have a better design they could share with me. Tom.

1 0

Haskell syntax files in Vim 6.0 has a bug !
by 안기영 14 Jan '02

14 Jan '02

The vim syntax file for literate haskell - lhaskell.vim - in my VIM. The version of my VIM is VIM - Vi IMproved 6.0 (2001 Sep 26, compiled Sep 26 2001 17:12:46) MS-Windows 32 bit GUI version with OLE support, Self extracting binary. you should change the line source syntax/haskell.vim to runtime! syntax/haskell.vim Also I edited the haskell syntax file - haskell.vim - to work with the \begin{code} \end{code} literate style too. It's a little tricky but this shall work good for most of the cases. I attached two files haskell.vim, lhaskell.vim. " Vim syntax file " Language: Haskell with literate comments " Maintainer: John Williams <jrw(a)pobox.com> " Last Change: 2001 May 09 " Enable literate comments let b:hs_literate_comments=1 " Include standard Haskell highlighting if version < 600 source <sfile>:p:h/haskell.vim else runtime! syntax/haskell.vim endif " vim: ts=8 " Vim syntax file " Language: Haskell " Maintainer: John Williams <jrw(a)pobox.com> " Last Change: 2001 Sep 02 " Thanks to Ryan Crumley for suggestions and John Meacham for " pointing out bugs. " " Options-assign a value to these variables to turn the option on: " " hs_highlight_delimiters - Highlight delimiter characters--users " with a light-colored background will " probably want to turn this on. " hs_highlight_boolean - Treat True and False as keywords. " hs_highlight_types - Treat names of primitive types as keywords. " hs_highlight_more_types - Treat names of other common types as keywords. " hs_highlight_debug - Highlight names of debugging functions. " Remove any old syntax stuff hanging around if version < 600 syn clear elseif exists("b:current_syntax") finish endif " (Qualified) identifiers (no default highlighting) syn match ConId "$\<[A-Z][a-zA-Z0-9_']*\.$\=\<[A-Z][a-zA-Z0-9_']*\>" syn match VarId "$\<[A-Z][a-zA-Z0-9_']*\.$\=\<[a-z][a-zA-Z0-9_']*\>" " Infix operators--most punctuation characters and any (qualified) identifier " enclosed in `backquotes`. An operator starting with : is a constructor, " others are variables (e.g. functions). syn match hsVarSym "$\<[A-Z][a-zA-Z0-9_']*\.$\=[-!#$%&\*\+/<=>\?@\\^|~.][-!#$%&\*\+/<=>\?@\\^|~:.]*" syn match hsConSym "$\<[A-Z][a-zA-Z0-9_']*\.$\=:[-!#$%&\*\+./<=>\?@\\^|~:]*" syn match hsVarSym "`$\<[A-Z][a-zA-Z0-9_']*\.$\=[a-z][a-zA-Z0-9_']*`" syn match hsConSym "`$\<[A-Z][a-zA-Z0-9_']*\.$\=[A-Z][a-zA-Z0-9_']*`" " Reserved symbols--cannot be overloaded. syn match hsDelimiter "(\|)\|\[\|\]\|,\|;\|_\|{\|}" " Strings and constants syn match hsSpecialChar contained "\\$[0-9]\+\|o[0-7]\+\|x[0-9a-fA-F]\+\|[\"\\'&\\abfnrtv]\|^[A-Z^_\[\\\]]$" syn match hsSpecialChar contained "\\$NUL\|SOH\|STX\|ETX\|EOT\|ENQ\|ACK\|BEL\|BS\|HT\|LF\|VT\|FF\|CR\|SO\|SI\|DLE\|DC1\|DC2\|DC3\|DC4\|NAK\|SYN\|ETB\|CAN\|EM\|SUB\|ESC\|FS\|GS\|RS\|US\|SP\|DEL$" syn match hsSpecialCharError contained "\\&\|'''\+" syn region hsString start=+"+ skip=+\\\\\|\\"+ end=+"+ contains=hsSpecialChar syn match hsCharacter "[^a-zA-Z0-9_']'$[^\\]\|\\[^']\+\|\\'$'"lc=1 contains=hsSpecialChar,hsSpecialCharError syn match hsCharacter "^'$[^\\]\|\\[^']\+\|\\'$'" contains=hsSpecialChar,hsSpecialCharError syn match hsNumber "\<[0-9]\+\>\|\<0[xX][0-9a-fA-F]\+\>\|\<0[oO][0-7]\+\>" syn match hsFloat "\<[0-9]\+\.[0-9]\+$[eE][-+]\=[0-9]\+$\=\>" " Keyword definitions. These must be patters instead of keywords " because otherwise they would match as keywords at the start of a " "literate" comment (see lhs.vim). syn match hsModule "\<module\>" syn match hsImport "\<import\>.*"he=s+6 contains=hsImportMod,hsVarSym,hsConSym syn match hsImportMod contained "\<$as\|qualified\|hiding$\>" syn match hsInfix "\<$infix\|infixl\|infixr$\>" syn match hsStructure "\<$class\|data\|deriving\|instance\|default\|where$\>" syn match hsTypedef "\<$type\|newtype$\>" syn match hsStatement "\<$do\|case\|of\|let\|in$\>" syn match hsConditional "\<$if\|then\|else$\>" " Not real keywords, but close. if exists("hs_highlight_boolean") " Boolean constants from the standard prelude. syn match hsBoolean "\<$True\|False$\>" endif if exists("hs_highlight_types") " Primitive types from the standard prelude and libraries. syn match hsType "\<$Int\|Integer\|Char\|Bool\|Float\|Double\|IO\|Void\|Addr\|Array\|String$\>" endif if exists("hs_highlight_more_types") " Types from the standard prelude libraries. syn match hsType "\<$Maybe\|Either\|Ratio\|Complex\|Ordering\|IOError\|IOResult\|ExitCode$\>" syn match hsMaybe "\<Nothing\>" syn match hsExitCode "\<$ExitSuccess$\>" syn match hsOrdering "\<$GT\|LT\|EQ$\>" endif if exists("hs_highlight_debug") " Debugging functions from the standard prelude. syn match hsDebug "\<$undefined\|error\|trace$\>" endif " Comments syn match hsLineComment "--.*" syn region hsBlockComment start="{-" end="-}" contains=hsBlockComment syn region hsPragma start="{-#" end="#-}" " Literate comments--any line not starting with '>' is a comment. if exists("b:hs_literate_comments") syn region hsLiterateComment start="^" end="^>" contains=hsLiterateCodeBlock syn region hsLiterateCodeBlock start="begin{code}" end="end{code}" contains=hsVarSym,hsConSym,hsString,hsCharacter,hsNumber,hsFloat,hsModule,hsImport,hsImportMod,hsInfix,hsStructure,hsStructure,hsTypedef,hsStatement,hsConditional,hsBoolean,hsType,hsMaybe,hsExitCode,hsOrdering,hsDebug,hsLineComment,hsBlockComment,hsPragma endif if !exists("hs_minlines") let hs_minlines = 50 endif exec "syn sync lines=" . hs_minlines if version >= 508 || !exists("did_hs_syntax_inits") if version < 508 let did_hs_syntax_inits = 1 command -nargs=+ HiLink hi link <args> else command -nargs=+ HiLink hi def link <args> endif hi link hsModule hsStructure hi link hsImport Include hi link hsImportMod hsImport hi link hsInfix PreProc hi link hsStructure Structure hi link hsStatement Statement hi link hsConditional Conditional hi link hsSpecialChar SpecialChar hi link hsTypedef Typedef hi link hsVarSym hsOperator hi link hsConSym hsOperator hi link hsOperator Operator if exists("hs_highlight_delimiters") " Some people find this highlighting distracting. hi link hsDelimiter Delimiter endif hi link hsSpecialCharError Error hi link hsString String hi link hsCharacter Character hi link hsNumber Number hi link hsFloat Float hi link hsConditional Conditional hi link hsLiterateComment hsComment hi link hsBlockComment hsComment hi link hsLineComment hsComment hi link hsComment Comment hi link hsPragma SpecialComment hi link hsBoolean Boolean hi link hsType Type hi link hsMaybe hsEnumConst hi link hsOrdering hsEnumConst hi link hsEnumConst Constant hi link hsDebug Debug delcommand HiLink endif let b:current_syntax = "haskell" " Options for vi: ts=8 sw=2 sts=2 nowrap noexpandtab ft=vim

1 0

Re: Haskell-Cafe digest, Vol 1 #293 - 4 msgs
by Jay Cox 12 Jan '02

12 Jan '02

> Message: 4 > From: Jorge Adriano <jadrian(a)mat.uc.pt> > To: haskell-cafe(a)haskell.org, glasgow-haskell-users(a)haskell.org > Subject: State Transformer > Date: Mon, 7 Jan 2002 15:41:57 +0000 > <snip> > Till then I had just read what I needed to be able to use the IO Monad. > Seems to me like having a State Transformer monad its the best way to do it. > Now I've read a great deal of Richard Birds Book chap 10 (Monads), as well as > the "Monads for the Haskell Working Programmer"[1] by Theodore Norvell. > > I was going to try to make my own simple examples using a ST. > A State Monad seemed something like would most probably be in some Standard > Library, or at least in some GHC library. > And it was (section 4.31.ST in the hslibs documentation) > I wanted to use this ST, but then I noticed it was different from the one > described in tutorial[1]. > > I was expecting the ST Monad ghc module to provide an apply function, > analogue to the > > applyST :: StateTrans s a -> s -> (s, a) > > applyST (ST p) s = p s I believe you want runST. its type is not > in the tutorial. > I also expected to have general functions to access and change State. I can't > implement them myself since the ST constructor is (obviously) not exported. > But this ST module seems to work in a completely diferent way. > >From what I can tell it is not suposed to be applyed to an initial state, > instead it starts with an 'empty' state... > State is controled with Referencies (mutable variables). yes, you can initialize any number of mutable variables from within the state monad. > Ok, now my problem, how do I use this? > > ---------------------------------------- > stupidFunc > runST ( > do { > initstate <- newSTRef ('x',0) > -- and now what? > }) > ----------------------------------------- > ----- import ST main = print (runST (do { x <-newSTRef 3;add1 x; y<-newSTRef "Elvis"; saysomething y; a<-readSTRef x; b<-readSTRef y; return (a,b)})) add1 a = do l <-readSTRef a writeSTRef a (l+1) saysomething y = modifySTRef y leftthebuilding leftthebuilding::String->String leftthebuilding x = x ++ " has left the building." ----- compile the above code with -package lang perhaps that'll give you some idea how to deal with STRefs and all. Jay Cox

1 0

differential operation (Typing Question!)
by Jay Cox 12 Jan '02

12 Jan '02

|> Message: 1 |> From: "Zhe Fu" <fuzh(a)cs.orst.edu> |> To: <haskell-cafe(a)haskell.org> |> Subject: how to implement the differential operation with Haskell? |> Date: Wed, 9 Jan 2002 00:37:20 -0800 |> |> Is there any built-in functions in Haskell to implement diffential |> operation? Or can anyone give me some advices about how to implement |them |> with Haskell? Thanks. If you happen to be talking about symbolically differentiating expressions, I happen to be in the early stage of developing a extendible module to do such a thing right now! However I seem to have come across some typing problems. But to understand my problem I may need to try to summarize the details thereof I started out with a recursive datatype >data BasDif r = Ext (r (BasDif r)) | > Symbol Sym | Constant Rational | > Sum (BasDif r) (BasDif r) | > Prod (BasDif r) (BasDif r) | > Divide (BasDif r) (BasDif r) | > Negate (BasDif r) | D (BasDif r) Notice the Ext( r (BasDif r)). I use this to extend the datatype. I define a basic differentiating function "d" on all of these constructs except Ext. When d pattern matches (Ext x) it calls some instance of the diff class on x. diff on some function g(u) where u is an expression returns a pair (u,g') back to "d" so that "d" can complete the chain rule d(g(u))=g'(u)*d(u). (technically it returns a function g' which takes two arguments: a data constructor and a BasDif expression of some sort the current expected typing of diff (forgive me for not knowing proper vernacular) is given below. >class Diff x where > diff:: Sym -> x a -> (a, (x a1 -> r (BasDif r)) -> a1 -> BasDif r) Its rather complex but I'll admit I stole it from the ghci interpreter giving me the type of function which did conceptually what I wanted it to do. the types are below. Differentiate> :type diffTrig forall t a a1 r. t -> Trig a -> (a, (Trig a1 -> r (BasDif r)) -> a1 -> BasDif r) Differentiate> :type diffNe forall t a a1 r. t -> NumExp a -> (a, (NumExp a1 -> r (BasDif r)) -> a1 -> BasDif r) Before I expound upon why the type needs to be so complicated, let me tell you what I'm trying to do with these diff functions that follow. (In the following definitions, prod, sum_, negate_, are more or less helper functions which make some trivial simplifications as they make products, sums, and additive inverses) >data NumExp a = N Rational a >diffNe s (N i x) = > let j = i-1 > in if (j /= 0 ) > then (x,\f-> \v -> prod (Ext(f (N (i-1) v))) (Constant i)) > else (x,\_-> \_->Constant 1) > >instance Diff NumExp where > diff=diffNe >data Trig a = Sin a | Cos a | Tan a | Cot a| Sec a |Csc a deriving Show >diffTrig s (Sin x) = (x, \f -> Ext . f . Cos) >diffTrig s (Cos x) = (x, \f -> negate_ . Ext . f . Sin) ... more defs >instance Diff Trig where > diff = diffTrig With these definitions, I have enough to take derivatives of (BasDif Trig) expressions or (BasDif NumExp) expressions, but not both. Therefore I defined the above expressions (as complicated as they are) so that I could make a instance of diff by combining the two without copy/pasting code (and without explicitly calling diffTrig and diffNe) thus being able to differentiate expressions of BasDif TrigNumExp (and thus being able to differentiate expressions with + - * / sine,cosine,tangent,their reciprocals and any combination thereof with a rational exponent) >data TrigNumExp a= T (Trig a) | NE (NumExp a) >instance Show a => Show (TrigNumExp a) where > showsPrec _ (T x) = shows x > showsPrec _ (NE x) = shows x > >diffTrigNumExp s (T x) = let (k,f)= diff s x in (k,\g->f (g .T)) >diffTrigNumExp s (NE x) = let (k,f)= diff s x in (k,\g->f (g .NE)) > >instance Diff TrigNumExp where > diff = diffTrigNumExp In this I have succeeded. THEN I tried to do the same for inverse trig functions. These are of a rather different nature. the derivative of inverse sine requires something to represent square roots of expressions, hence I use the constructor for NE expressions. >diffArcT s (ArcSin x) =(x,\f-> \y->Ext(f ( N (-1/2) > (sum_ (Constant 1) (negate_ (prod y y)))))) >diffArcT s _ = error "incomplete" the type of diffArcT is Differentiate> :type diffArcT forall t a r1 r. t -> ArcTrig a -> (a, (NumExp (BasDif r1) -> r (BasDif r)) -> BasDif r1 -> BasDif r) I suppose the error message I get when adding this function to the module is understandable given the class constraints.. ... Differentiate.v2.lhs:177: Couldn't match `ArcTrig a1' against `NumExp (BasDif r)' Expected type: Sym -> ArcTrig a -> (a, (ArcTrig a1 -> r1 (BasDif r1)) -> a1 -> BasDif r1) Inferred type: Sym -> ArcTrig a -> (a, (NumExp (BasDif r) -> r2 (BasDif r2)) -> BasDif r -> BasDif r2) In the definition of `diff': diffArcT ... but seems to me to be a reasonable relaxing of types for the class doesn't work either (in fact it produces errors for every instance of diff ... Old class >class Diff x where > diff:: Sym -> x a -> (a, (x a1 -> r (BasDif r)) -> a1 -> BasDif r) New class class Diff x where diff:: Sym -> x a -> (a, (x1 a1 -> r (BasDif r)) -> a1 -> BasDif r) New errors with new class Cannot unify the type-signature variable `x1' with the type `TrigNumExp' Expected type: Sym -> TrigNumExp a -> (a, (x1 a1 -> r (BasDif r)) -> a1 -> BasDif r) Inferred type: Sym -> TrigNumExp a -> (a, (TrigNumExp a11 -> r1 (BasDif r1)) -> a11 -> BasDif r1) In the definition of `diff': diffTrigNumExp Differentiate.v2.lhs:177: Cannot unify the type-signature variable `x1' with the type `NumExp' Expected type: Sym -> ArcTrig a -> (a, (x1 a1 -> r (BasDif r)) -> a1 -> BasDif r) Inferred type: Sym -> ArcTrig a -> (a, (NumExp (BasDif r1) -> r2 (BasDif r2)) -> BasDif r1 -> BasDif r2) ... etc. What I don't understand is WHY NumExp cannot be unified with x1. what I would personally would like to understand is if Haskell's Hindley-Miller type system can even deal with what I want to do (basically I want a type for diff such that the definition of diffArcT would be tolerable to the compiler.) I realize I am a bit over my head here so it might be concievable that just some pointer to a reference on how haskell deals with type resolution might help as well, or perhaps some general method for concieving of a general type for a member of a class, or perhaps some ideas to re-engineer this module. Anyway, I suppose this module might be of some interest to some people so I have put it in a temporary place so that some people may play with it. It doesnt have any functions for reading general expresssions yet, you could enter some funky multivariable expression and see what comes out. (I must warn you, if you happen to use the "d" function, it doesnt do much but the simplest simplifications. some of the less trivial simplifications have been commented out because they do not help the runtime. It is at (temporarely) http://home.flash.net/~flygal/Jay/Haskell/Differentiate/v0.1/Differentiate.… Have fun and thanks for any help Jay Cox

1 0