[Haskell-cafe] Typechecker to GADT: the full implementation of a typed DSL

2007-10-04 Thread oleg
Pasqualino 'Titto' Assini wrote: I am trying to write an interpreter for a little functional language but I am finding very problematic to dynamically create a typed representations of the language terms. The problem is to write a function that converts between Exp and Term t as in:

[Haskell-cafe] Typed DSL compiler, or converting from an existential to a concrete type

2007-10-06 Thread oleg
The earlier message showed how to implement a typechecker from untyped AST to wrapped typed terms. The complete code can be found at http://okmij.org/ftp//Haskell/staged/TypecheckedDSL.hs The typechecker has the type typecheck :: Gamma - Exp - Either String TypedTerm where

[Haskell-cafe] Implementing the State Monad

2007-11-11 Thread oleg
apfelmus showed the implementation of the state monad as free term algebra, using GADT. Here's an implementation that does not use GADT http://okmij.org/ftp/Haskell/types.html#state-algebra All the smarts are in the observation function. This style is _very_ well explained by Ralf Hinze

[Haskell-cafe] Re: Guidance on using asynchronous exceptions

2007-11-16 Thread oleg
Yang wrote: Furthermore, is there any way to embed this information [about async execptions] in the type system, so that Haskellers don't produce async-exception-unaware code? (Effectively, introducing checked interrupts?) Yes, it is possible to make the information about exceptions and

[Haskell-cafe] Re: distinguish functions from non-functions in a class/instances

2007-12-07 Thread oleg
Philipp N. wrote: i'm trying to wrap functions (a - b - ... - z) of any arity to functions of type ([String] - y), where list of strings replaces the typed arguments. the problem is, that you cannot distinguish type (x-y) from z, so these instances are overlapping. to which apfelmus replied

[Haskell-cafe] Dynamic typing of polymorphic functions

2007-12-20 Thread oleg
Alfonso Acosta wrote: mapSY :: (Typeable a, Typeable b) = (a - b) - Signal a - Signal b mapSY f (Signal primSig) = Signal (PrimSignal (MapSY (toDyn f) primSig)) The following process would be really useful but its compilation obviously fails: mapSnd :: Signal (a, a) - Signal a mapSnd =

[Haskell-cafe] Re: type trickery

2007-12-20 Thread oleg
Adrian Neumann wrote: I figured I'd need something like this data GF = GF Integer Integer so that each element of the finite field would remember p. However I can't think of a way to use the typesystem to ensure that p is always the same. You might like: Vectro: Haskell library

[Haskell-cafe] Re: Applying a Dynamic function to a container of Dynamics

2007-12-22 Thread oleg
Alfonso Acosta wrote: dynApp allows to apply a Dynamic function to a Dynamic argument: dynApp :: Dynamic - Dynamic - Dynamic I don't seem to find a way (without modifying Data.Dynamic itself) to code this function This is not very difficult if we have a well-delineated (and still infinite)

[Haskell-cafe] Re: more thoughts on Finally tagless

2010-03-09 Thread oleg
Stephen Tetley wrote: The finally tagless style is an implementation of the TypeCase pattern (Bruno C. d. S. Oliveira and Jeremy Gibbons): http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/typecase.pdf The finally tagless style is slightly more general. The TypeCase paper emphasizes

[Haskell-cafe] Re: explicit big lambdas

2010-03-19 Thread oleg
Paul Brauner wrote: is there a way in some haskell extension to explicit (system F's) big lambdas and (term Type) applications in order to help type inference? Actually, yes: newtype constructor introductions may act as a big lambda, with constructor elimination acting as type applications:

[Haskell-cafe] Leibniz equality can be made injective

2010-05-02 Thread oleg
We show that type families let us write Leibniz equality witnesses of the injectivity of type constructors. We may use Leibniz equality not only for introduction but also for elimination. The paper on ``Typing Dynamic Typing'' (Baars and Swierstra, ICFP 2002) demonstrated the first

[Haskell-cafe] Type famillies Lifting IO

2010-05-20 Thread oleg
Maciej Piechotka wrote: class (Monad m, Monad (IO' m)) = MonadIO m where type IO' m :: * - * liftIO :: IO a - IO' m a liftM :: m a - IO' m a The signature for liftIO betrays a problem. Since liftIO is a member of a type class, when liftIO is used in code, the type checker has to

[Haskell-cafe] Existentials and SYB [Was: GADTs and Scrap your Boilerplate]

2010-05-21 Thread oleg
Oscar Finnsson wrote: I got the GADT data DataBox where DataBox :: (Show d, Eq d, Data d) = d - DataBox and I'm trying to get this to compile instance Data DataBox where gfoldl k z (DataBox d) = z DataBox `k` d gunfold k z c = k (z DataBox) -- not OK As has been pointed out,

[Haskell-cafe] SYB with Existentials

2010-05-26 Thread oleg
It is quite straightforward to extend the SYB generic programming framework to existential data types, including existential data types with type class constraints. After all, an existential is essentially a variant data type with the infinite, in general, number of variants. The only,

[Haskell-cafe] Re: SYB with Existentials

2010-05-28 Thread oleg
Under what license are you releasing DataEx.hs? I'm wondering if I may use it in my package (under BSD3 license) until something like it is included in SYB. DataEx.hs as other such code of mine has been written in the hope it might be useful, or at least instructive. I usually place such code

[Haskell-cafe] Tricks with GMap -- question about conflicts w/ indexed type families

2010-06-08 Thread oleg
Ryan Newton wrote: What I would next *like* to do is something like the following: import qualified Data.IntMap as DI instance FitInWord t = GMapKey t where data GMap t v = GMapInt (DI.IntMap v) deriving Show The problem is that there's already a more general instance of

[Haskell-cafe] Re: checking types with type families

2010-07-01 Thread oleg
Simon Peyton-Jones wrote: Until now, no one has know how to combine fundeps and local constraints. For example class C a b | a-b where op :: a - b instance C Int Bool where op n = n0 data T a where T1 :: T a T2 :: T Int -- Does this typecheck? f :: C a b

[Haskell-cafe] Undecidable Instances [Was: Is my code too complicated?]

2010-07-04 Thread oleg
Ertugrul Soeylemez wrote: Essentially UndecidableInstances turns the type system into a Turing-complete programming language. One direct consequence is that type checking may not terminate Actually, the type checking (specifically, instance resolution) always terminates, due to the recursion

[Haskell-cafe] Collecting MonadError errors generically

2010-07-14 Thread oleg
Leon Grynszpan wrote: What I want, instead, is to run a whole bunch of computations that may throw errors. If there are any errors, I want to collect them all into one big master error. If not, I want a list of results. Here's an example of usage: couldThrowError :: (Error e, MonadError e

[Haskell-cafe] Re: in-equality type constraint?

2010-07-17 Thread oleg
Ryan Ingram wrote: But it doesn't generalize; you need to create a witness of inequality for every pair of types you care about. One can do better, avoiding the quadratic explosion. One merely needs to establish a map from a type to a suitable, comparable representation -- for example, to a

[Haskell-cafe] Re: Tiger compiler in Haskell: annotating abstract syntax tree

2010-07-20 Thread oleg
Jose' Romildo Malaquias wrote: I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell. There is also a general way of annotating AST post factum, described in

Re: [Haskell-cafe] Re: Tiger compiler in Haskell: annotating abstract

2010-07-21 Thread oleg
Jose Pedro Magalhaes wrote: From what I understand, you are using a list of integers to encode a path to a subterm. This is a practical and lightweight implementation, but less type-safe: it is easy to encode annotations that do not correspond to any value. Also, it cannot guarantee, with

[Haskell-cafe] Re: Instances for Set of Functor, Traversable?

2010-07-27 Thread oleg
Lennart Augustsson wrote: Try to make Set an instance of Functor and you'll see why it isn't. It's very annoying. And yet the very simple, and old solution works. http://okmij.org/ftp/Haskell/types.html#restricted-datatypes We just properly generalize Functor, so that all old

[Haskell-cafe] Re: Type Families: deleting from HList

2010-08-04 Thread oleg
Serguey Zefirov wrote: Is it possible to delete an element from heterogenous list using type families alone? I can do it using multiparameter type classes: class Del a list result instance Del a (a,list) list instance Del a list list' = Del a (a',list) list' instance Del a () () I'm

[Haskell-cafe] Re: Inferring types from functional dependencies

2006-06-10 Thread oleg
Jeff Harper defined typeclasses class Reciprocate a b | a - b where recip :: a - b class Multiply a b c | a b - c where (*) :: a - b - c and encountered the problem with -- Here I define a default (/) operator that uses the -- Reciprocate and Multiply class to perform division.

[Haskell-cafe] Functional programming for processing of large raster images

2006-06-21 Thread oleg
Recently Vo Minh Thu wondered if Haskell (or, I generalize, functional programming) can be of much use for computer graphics programming. I'd like to point out a project that experimentally shown that functional programming is of great help for processing of large raster images (24-bit PPM

[Haskell-cafe] Re: Functional _meta_programming for processing of large raster images

2006-06-21 Thread oleg
I'm afraid the _meta_ programming aspect of the image processing project may be overlooked. Joel Reymont wrote: I think the issue wasn't using functional programming for large image processing, it was using Haskell. OCaml is notoriously fast and strict. Haskell/GHC is... lazy. Well, in

[Haskell-cafe] Re: technique to allow innocuous ambiguity in instance declarations?

2006-07-11 Thread oleg
. The idea is similar to the one described in http://pobox.com/~oleg/ftp/Haskell/types.html#is-function-type The complete code follows. Now testx typechecks. {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} {-# OPTIONS -fallow-overlapping-instances #-} module

[Haskell-cafe] Type level logic programming terminology

2006-07-20 Thread oleg
Most systems of (first-order) logic differentiate between function letters (aka, symbols) and predicate letters (symbols). The former are used to build terms; the latter build atomic formulas (which can later be combined in more complex formulas using negation, conjunction, disjunction, and

[Haskell-cafe] Local functional dependencies: solving show . read and XML generation problems

2006-08-14 Thread oleg
Sorry for a late reply, I'm out of town. As I understand it, the problem is as follows: we'd like to construct different realizations of XML documents from data of different types. We wish to write p (p foo) and specify the desired type of the XML document, like (p (p foo)) ::

[Haskell-cafe] head as a total function

2006-09-07 Thread oleg
be handled. Again, without introducing any runtime overhead: http://pobox.com/~oleg/ftp/Haskell/KMP-deptype.hs The approach is formalizable; the recent PLPV talk by Chung-chieh Shan presented the types systems and the proof techniques. Some of the proofs have been formalized in Twelf: http

[Haskell-cafe] Re: variadic functions and typeCast

2006-09-27 Thread oleg
, please see any code described in http://pobox.com/~oleg/ftp/Haskell/typecast.html Appendix D of the full HList paper (or, HList technical report, I should say) gives the reasons for TypeCast. Briefly, TypeCast lets us replace a (ground) type T with a type variable t subject

[Haskell-cafe] Typeclass vs. Prolog programming

2006-09-28 Thread oleg
This message is intended as a long answer to Michael Shulman's question (Re: variadic functions and typeCast) and Jason Dagit's question (Re: Duplicate Instance problem). Incidentally, the short answer to Jason Dagit's question is `constraints are disregarded during instance selection'. The

[Haskell-cafe] Re: Typeclass vs. Prolog programming

2006-09-30 Thread oleg
I previously wrote: The typechecker commits to the instance and adds to the current constraints TypeCast x Int, Ord Bool, Eq Bool The latter two are obviously satisfied and so discharged. The former leads to the substitution {x-Int}. I should have been more precise and said:

[Haskell-cafe] irrefutable patterns for existential types / GADTs

2006-09-30 Thread oleg
It seems that irrefutable pattern match with existentials is safe. The fact that irrefutable pattern match with GADT is unsafe has been demonstrated back in September 2004. Let us consider the following regular existential data type data TFoo where Foo :: Show a = a - TFoo Bar :: Int -

[Haskell-cafe] Problematic irrefutable pattern matching of existentials

2006-10-01 Thread oleg
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

[Haskell-cafe] Re: OOHaskell problems

2006-10-04 Thread oleg
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/ both HList and OOHaskell are now available via DARCS http://darcs.haskell.org/HList/

[Haskell-cafe] Trying to understand HList / hMapOut

2006-10-07 Thread oleg
I am using a heterogenous list as in [1] all elements of which are of a given class C. Since foo maps all class members to Int, hMapOut should be a straight-forward way to produce homogenous Int lists from heterogenous CLists: test :: (CList l) = l - [Int] test = hMapOut foo Well, `foo'

[Haskell-cafe] Re: Trying to understand HList / hSequence now [why it works]

2006-10-10 Thread oleg
Matthias Fischmann wrote: instance (Monad m, HSequence m HNil HNil) = HSequence m HNil HNil where hSequence _ = return HNil how can i use the goal of the declaration as one of the conditions without causing some sort of black hole in the type inference algorithm? Very easily: the

[Haskell-cafe] Re: type level functions (type of decreasing list)

2006-10-18 Thread oleg
. This example shows that Haskell truly has more kinds than it is commonly acknowledged. For more details on constrained lists (list of odd numerals, even numerals, etc), please see the following implementation of Tim Sheard's `Half' example http://pobox.com/~oleg/ftp/Haskell/Half.hs data Succ a = S

[Haskell-cafe] Re: 6.4 - 6.6, scoped type variables

2006-10-18 Thread oleg
I too miss the old way of handling local type variables. Previously, local type annotations worked a lot like an additional constraint, with type variables denoting some type. The same type variable denoted the same type. Here's how it works in OCaml, for example: # let pair x y = (x,y);; val

[Haskell-cafe] Re: Strictness, order of IO operations: NewCGI HDBC

2006-10-20 Thread oleg
Tim Smith wrote: Has anyone found out how to lift bracket into another monad? Yes, please see the thread `Re: Control.Exceptions and MonadIO' staring at http://www.haskell.org/pipermail/haskell-cafe/2006-April/015444.html There is also a Haskell' ticket:

[Haskell-cafe] Re: function types as instances of Num

2006-10-29 Thread oleg
The problem seems equivalent to the following: http://pobox.com/~oleg/ftp/Haskell/typecast.html#local-fd That is, the inferred type is too general to chose the appropriate instance. The solution is also the same: either add type annotations to restrict the inferred type (and so make

[Haskell-cafe] An example of dependent types [was: Simple GADT parser for the eval example]

2006-11-01 Thread oleg
Greg Buchholz has posed an interesting problem of writing a typechecker. Given untyped terms of the form data Expr = ELit Int | EInc Expr | EIsZ Expr we are to compute typed terms: data Term a where Lit :: Int - Term Int Inc :: Term Int -

[Haskell-cafe] Re: Debugging partial functions by the rules

2006-11-15 Thread oleg
Donald Bruce Stewart wrote: So all this talk of locating head [] and fromJust failures got me thinking: Couldn't we just use rewrite rules to rewrite *transparently* all uses of fromJust to safeFromJust, tagging the call site with a location? I'm sorry for shifting the topic:

Re: [Haskell-cafe] Re: Debugging partial functions by the rules

2006-11-15 Thread oleg
are statically assured of no head [] error! test2 = head $ 1 !: 2 !: 3 !: [] This would look better had `[1,2,3]' been a rebindable syntax similar to `do'. I should point to http://pobox.com/~oleg/ftp/Computation/lightweight-dependent-typing.html for further, more complex examples. We can also

Re: [Haskell-cafe] Re: Debugging partial functions by the rules

2006-11-15 Thread oleg
Jan-Willem Maessen wrote: In addition, we have this rather nice assembly of functions which work on ordinary lists. Sadly, rewriting them all to also work on NonEmptyList or MySpecialInvariantList is a nontrivial task. That's an excellent question. Indeed, let us assume we have a

[Haskell-cafe] Re: How to get subset of a list?

2006-11-30 Thread oleg
Huazhi (Hank) Gong wrote: Like given a string list s=This is the string I want to test, I want to get the substring. In ruby or other language, it's simple like s[2..10], but how to do it in Haskell? Quite simply, actually: infixl 1 %% str %% idxs = map (str !!) idxs That is it. Not the

[Haskell-cafe] Well-typed functions with nonexisting signatures [Was: type variable question]

2006-12-14 Thread oleg
Nicolas Frisby wrote The commented out signature is the signature that GHC infers for the function. When I uncomment that signature, it will no longer type check. Why does this happen? Even with the forall and the explicit signatures in the where clause, it chokes. Alas, this is the property

[Haskell-cafe] MapTuple is possible and easy

2007-01-11 Thread oleg
Marco Tu'lio Gontijo e Silva wrote: is there a way to defined something as a map to use in tuples? Yes, it is: and it is quite easy and straightforward. Udo Stenzel since c would be a variable that ranges over type classes, and that doesn't exist. Of course it does: please see below (as

[Haskell-cafe] restricted existential datatypes

2007-01-11 Thread oleg
Misha Aizatulin wrote I am using existential boxes like data Box cxt = forall a . Sat (cxt a) = Box a here Sat is taken from [1]: class Sat a where dict :: a The result is a box type which can have variable context imposed on its contents. What I noticed is that sometimes I want to

[Haskell-cafe] Are GADTs expressive? Simple proof-carrying code in Haskell98

2007-01-13 Thread oleg
that is convertible to typeclasses in the straightforward way, see for example, http://pobox.com/~oleg/ftp/Haskell/GADT-interpreter.hs Inn this particular example, GADT do not bring any power. Incidentally, the typeclass encoding has an advantage: If the submitted proof is invalid, the error

[Haskell-cafe] Genuine Eratosthenes sieve [Was: Optimization fun]

2007-02-11 Thread oleg
It has been already remarked that any algorithm of finding prime numbers that uses division or `mod` operations cannot be called (Eratosthenes) sieve. The insight of Eratosthenes is finding primes without resorting to division or multiplication. In his time, doing either of those operations was

[Haskell-cafe] Even better Eratosthenes sieve and lucky numbers

2007-02-12 Thread oleg
We further simplify the previously posted genuine sieve algorithm and generalize it to the finding of lucky numbers. We observe that we only need to store marks _signifying_ the integers, but never the integers themselves. Thus we arrive at the algorithm that is distinguished from all

[Haskell-cafe] Type-level lambdas in Haskell?

2007-02-21 Thread oleg
On 2/21/07, Alfonso Acosta alfonso.acosta at gmail.com wrote: In my opinion adding Type-level lambdas would be the way to go, but they unfortunately are not part of Haskell. Type-level lambdas are already present in Haskell. Please see the messages On computable types. I. Typed lambda and

[Haskell-cafe] Type-level lambdas in Haskell? ( was Multiparameter class error)

2007-02-21 Thread oleg
Alfonso Acosta wrote: class Synchronous s f1 f2 | s - f1, s - f2 where mapSY :: f1 a b - s a - s b delaySY:: a - s a - s a zipWithSY :: f2 a b c- s a - s b - s c The goal of this class is to extend the name of the following functions (which BTW are already

[Haskell-cafe] Re: Code and Perf. Data for Prime Finders

2007-02-23 Thread oleg
Perhaps you might want include in your test the following: http://www.haskell.org/pipermail/haskell-cafe/2007-February/022437.html It seems quite close to the genuine Eratosthenes sieve algorithm: it employs the idea of marks, it can cross composite numbers off several times, and it never

[Haskell-cafe] overlapping instances, selecting if type a does not belong to class?

2007-02-26 Thread oleg
complaint. That said, it is quite possible in Haskell to achieve genuine class-based dispatch, with backtracking if necessary: http://pobox.com/~oleg/ftp/Haskell/poly2.txt However, it seems that your particular problem can be solved with simpler means: instance (HList

[Haskell-cafe] Safe lists with GADT's

2007-02-26 Thread oleg
Stefan O'Rear wrote: Personally I like the GADT approach best since it is very flexible and convienient. I have never used a purpose-build computer proof system, but (modulo _|_) it took me less than 10 minutes to answer LoganCapaldo (on #haskell)'s challenge to proof that + was commutative

[Haskell-cafe] OO Design in Haskell Example (Draft)

2007-02-26 Thread oleg
Steve Downey wrote: In the last OO design in Haskell thread (and probably in every one preceeding it), it was suggested that having some examples might be a good idea. Since most people with existing designs will have some familiarity with Design Patterns, and those are typical building

[Haskell-cafe] Re: overlapping instances, selecting if type a does not belong to class?

2007-02-27 Thread oleg
uses the results of the analysis. I wasn't able to find the definition of AllOf(But): It is in the complete code http://pobox.com/~oleg/ftp/Haskell/poly2.hs It isn't that interesting: data AllOfBut x y {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances

[Haskell-cafe] Takusen and strictness, and perils of getContents

2007-03-02 Thread oleg
Takusen permits on-demand processing on three different levels. It is specifically designed for database processing in bounded memory with predictable resource utilization and no resource leaks. But first, about getContents. It has been mentioned a while ago that getContents should be renamed to

[Haskell-cafe] Re: HList error with hFoldr

2008-01-27 Thread oleg
After some fooling around, I came up with something I think makes sense. Let me know if this is the right/wrong thing. It seems to work for the examples I've tried so far. instance (Floating f, MetricSpace e f ,MetricSpace e' f, HZip l l (HCons (e', e') l') ,HFoldr

[Haskell-cafe] Designing DSL with explicit sharing [was: I love purity, but it's killing me]

2008-02-13 Thread oleg
Tom Hawkins wrote: ] My DSLs invariably define a datatype to capture expressions; something ] like this: ] ] data Expression ] = Add Expression Expression ] | Sub Expression Expression ] | Variable String ] | Constant Int ] deriving Eq ] The problem comes when I want to generate

[Haskell-cafe] Designing DSL with explicit sharing [was: I love purity, but it's killing me]

2008-02-14 Thread oleg
Matthew Naylor wrote: it's not immediately clear (to me at least) how efficient your method will be in practice. Any method based on common sub-expression elimination surely must inspect every node in the flattened graph. In the worst case, an acyclic graph containing n nodes could have 2^n

[Haskell-cafe] Haskell w/ delimited continuations

2008-02-23 Thread oleg
Call-by-name lambda-calculus is strictly more expressive (in Felleisen sense) than call-by-value lambda-calculus, and the call-by-need (aka, lazy) lambda-calculus is observationally equivalent to the call-by-name. One can add shift/reset to any of these calculi (CBV shift/reset is most known;

[Haskell-cafe] Instance selection based on a class constraint [was: Issues(Bugs?) with GHC Type Families]

2008-03-11 Thread oleg
Manuel M T Chakravarty: Hugo Pacheco: I would simply like the compiler not to use that instance if the equality constraint does not hold, like some another instance dependency constraint, but I assume that is not possible. This is independent of type families. The selection of type

[Haskell-cafe] Exception handling when using STUArray

2008-03-11 Thread oleg
Sterling Clover wrote: there's no standard way that I know of besides inspection to determine if code might throw an exception, and this is particularly the case with the dreaded lazy IO of prelude functions. The following old message showed even two ways of doing exactly that -- in Haskell,

[Haskell-cafe] Re: Reflective capabilities of Haskell (cont'd)

2008-03-13 Thread oleg
Martin Hofmann wrote: Thanks a lot, this helps a bit, but access to function bodies is exactly what I need. Then perhaps you might like the method of reconstructing bodies (of possibly compiled) functions http://okmij.org/ftp/Computation/Generative.html#diff-th in the form of AST --

[Haskell-cafe] Monad instance for Data.Set

2008-03-24 Thread oleg
The following code solves exactly the problem of implementing (restricted) MonadPlus in terms of Data.Set: http://okmij.org/ftp/Haskell/DoRestrictedM.hs The code is written to demonstrate the do-notation. We write the monadic code as usual: test1s_do () = do x - return a return

[Haskell-cafe] Re: Trying to avoid duplicate instances

2008-05-14 Thread oleg
Eric Stansifer wrote: I am using a bunch of empty type classes to categorize some objects: class FiniteSolidObject o class FinitePatchObject o class InfiniteSolidObject o Since solid objects are exactly finite solid objects plus infinite solid objects, there is an obvious way to code

[Haskell-cafe] Re: number-parameterized types and heterogeneous lists

2008-06-23 Thread oleg
Luke Palmer wrote in response to Harald ROTTER I also wonder if there is some kind of generalized foldr such that, e.g. D1 $ D0 $ D0 $ Sz = specialFoldr ($) Sz [D1,D0,D0] I think that this foldr must be some special foldr that augments the data type of the result in each foldr step.

[Haskell-cafe] CBN, CBV, Lazy in the same final tagless framework

2009-10-08 Thread oleg
Actually it is possible to implement all three evaluation orders within the same final tagless framework, using the same interpretation of types and reusing most of the code save the semantics of lam. That is where the three orders differ, by their own definition. In call-by-name, we have

[Haskell-cafe] What *is* a DSL?

2009-10-08 Thread oleg
Perhaps it would be appropriate to point out the IFIP conference on exactly that topic, DSL. The conference took place in July, here is the permanent record: http://dsl09.blogspot.com/ with pointers to the slides and the discussions. The panel discussion has debated that very question,

[Haskell-cafe] Re: Applicative do?

2009-10-10 Thread oleg
It seems the applicative do is almost identical to the form ML and Scheme has had since the beginning. Perhaps that semantic similarity might inform the syntactic debate. do a - f g b - h pure $ foo a b into this: (\a b - pure $ foo a b) * (f * g * h) This form, although very

[Haskell-cafe] (no subject)

2009-10-13 Thread oleg
Martin Sulzmann wrote: Undecidable instances means that there exists a program for which there's an infinite reduction sequence. I believe this may be too strong of a statement. There exists patently terminating type families that still require undecidable instances in GHC. Here is an example:

[Haskell-cafe] Re: Relational Algebra

2009-10-16 Thread oleg
In hindsight it occurred to me that the algorithm can be abstractly expressed in terms of relational algebra for which I need an EDSL. One concrete implementation could then be an interpreter / compiler to SQL, if I choose to use a database backend, and another implementation could be a

[Haskell-cafe] Re: [Haskell-beginners] map question

2009-10-20 Thread oleg
Something I wonder from time to time if it would be a good thing or not is to allow a `f g` b to mean f g a b You don't have to wonder: http://www.haskell.org/haskellwiki/Infix_expressions Granted, you have to use different characters rather than the backquote. On the other

[Haskell-cafe] Re: Finally tagless and ghc-extensions

2009-10-30 Thread oleg
and Caml lists). P.S. I'm still digesting the Finally Tagless approach from Oleg, Jacques and Chen. You probably mean Chung-chieh Shan, whose last name is Shan and the first name is Chung-chieh. http://en.wikipedia.org/wiki/Chinese_name

[Haskell-cafe] Re: How to fulfill the code-reuse destiny of OOP?

2009-10-30 Thread oleg
Magicloud Magiclouds wrote In OOP, when I inherit a class, I also got the members of it. But in haskell, how to inherit a data? Although any OOP system has by definition, objects, not all of them have classes. The best example of a classless (also called 1-level, or prototype-based) OO

[Haskell-cafe] Type-indexed expressions with fixpoint

2009-11-10 Thread oleg
Brent Yorgey wrote: This email is literate Haskell. I'm struggling to come up with the right way to add a fixpoint constructor to an expression language described by a type-indexed GADT (details below). but since Haskell doesn't have type-level lambdas, I don't see how to make that work.

[Haskell-cafe] Re: Iteratee question

2009-11-26 Thread oleg
Valery V. Vorotyntsev wrote: The following pattern appears quite often in my code: results - map someConversion `liftM` replicateM nbytes Iter.head The meaning is: take `nbytes' from stream, apply `someConversion' to every byte and return the list of `results'. But there's more than one

[Haskell-cafe] Parsec-like parser combinator that handles left recursion?

2009-12-09 Thread oleg
There are at least two parser combinator libraries that can deal with *any* left-recursive grammars. That said, Prof. Swierstra's advice to try to get rid of left recursion is still well worth to follow. The first library is described in Frost, Richard, Hafiz, Rahmatullah, and

[Haskell-cafe] Re: Type system speculation

2009-12-09 Thread oleg
Andrew Coppin wrote: What we're really trying to do here is attach additional information to a value - information which exists only in the type checker's head, but has no effect on runtime behaviour (other than determining whether we *get* to runtime). As far as I can tell, Haskell does not

[Haskell-cafe] Re: Why doesn't laziness save the day here?

2010-01-05 Thread oleg
Dale Jordan wrote: The motivation for iterateR is to be able to have the ultimate consumer determine how many random values to force, but still have a single random generator used throughout the computation. My intuition tells me that since the infinite list is produced in finite batches,

[Haskell-cafe] Re: Non-termination of type-checking

2010-01-28 Thread oleg
Here is a bit more simplified version of the example. The example has no value level recursion and no overt recursive types, and no impredicative polymorphism. The key is the observation, made earlier, that two types c (c ()) and R (c ()) unify when c = R. Although the GADTs R c below is

[Haskell-cafe] Re: Non-termination of type-checking

2010-01-30 Thread oleg
We explain the technique of systematically deriving absurd terms and apply it to type families. Indeed I should have said that there is no _overt_ impredicative polymorphism in the example posted earlier: it is precisely the impredicative polymorphism that causes the paradox. As everybody

[Haskell-cafe] HList darcs repo

2010-02-03 Thread oleg
HList (and OOHaskell, for that matter) are now hosted on community.haskell.org, in the directories /srv/code/HList /srv/code/OOHaskell The repositories are also available at these URLs: http://code.haskell.org/HList/ http://code.haskell.org/OOHaskell/ Many

[Haskell-cafe] Re: Pointfree composition for higher arity

2010-02-17 Thread oleg
Sean Leather wrote: (...) :: (c - d) - (a - b - c) - a - b - d (...) f g x y = f (g x y) Does anybody else care about this? What are some alternative solutions? Here is a different solution: http://okmij.org/ftp/Haskell/polyvariadic.html#polyvar-comp f:: a1-a2- -cp (where

[Haskell-cafe] Re: Point-free style (Was: Things to avoid)

2005-02-10 Thread oleg
contains the type signature to increase comprehension: prod:: (MCompose a b (c - d) e, MCompose f g (b,g) d) = (h - a) - (c - f) - h - e prod = (. ((. (,)) . mcomp)) . mcomp Here `prod' is indeed the categorical product. The second example is taken from http://pobox.com/~oleg/ftp

[Haskell-cafe] Automatic pointless translation

2005-02-14 Thread oleg
This message is a literate Haskell98 code for translating proper linear combinators into a point-free style. That is, we will be converting (closed, albeit that is not strictly a requirement) terms of the form ``\x1 ... xn - term'' where each variable xi has at most one occurrence in term. The

[Haskell-cafe] Re: (Newbie) Dynamic Programming, Memoizing Etc.

2005-03-16 Thread oleg
Bryce Bockman wrote: How would you guys memoize the following code. simpleCalc :: (Int,Int) - (Int,Int) simpleCalc (1,l) = (1,l+1) simpleCalc (x,l) | (odd x) = simpleCalc (((3*x) + 1), 1 + l) | otherwise = simpleCalc ((x `div` 2), 1 + l) sCalc x = simpleCalc (x,0)

[Haskell-cafe] Re: Best practices for modular programming in Haskell

2005-03-16 Thread oleg
Benjamin Pierce wrote: For someone coming to Haskell from an OCaml background, one of the hardest things to get used to is the somewhat more bare bones module system that Haskell provides. ... This works fine as long as what you're exporting is just values, but it's awkward for types, since

[Haskell-cafe] Simulating OO programming with type classes; writing a factory fu nction

2005-06-01 Thread oleg
Alistair Bayley wrote: There's a small problem: how to write a factory function that returns values of various subtypes. The makeSubType function below won't compile, obviously because the returns types are different (they're not the same 'm'). Indeed, expressions in both branches of an `if'

[Haskell-cafe] Re: Control.Monad.Cont fun

2005-07-07 Thread oleg
program). The CC monad transformer (derived from the CC library by Sabry, Dybvig, Peyton-Jones), freely available from http://pobox.com/~oleg/ftp/packages/LogicT.tar.gz is free from that drawback. BTW, with that monad transformer, the example looks as follows (again, in a de-sugared way

RE: [Haskell-cafe] Overlapping Instances with Functional Dependencies

2005-07-11 Thread oleg
Daniel Brown wrote: class Baz a b | a - b instance Baz (a - b) (a - [b]) instance Baz a a ...but Baz fails with this error... When confronted with overlapping instances, the compiler chooses the most specific one (if it is unique), e.g. `Baz (a - b) (a - [b])` is more specific

[Haskell-cafe] Re: Lists vs. Monads

2005-07-17 Thread oleg
of that derivation is a note `How to take a TAIL of a functional stream' http://pobox.com/~oleg/ftp/Computation/Continuations.html#cdr-fstream The higher-rank type is needed only to express the polymorphic answertype. ___ Haskell-Cafe mailing list Haskell-Cafe

[Haskell-cafe] Re: [Haskell] Re: A MonadPlusT with fair operations and pruning

2005-07-18 Thread oleg
Regarding the law of mif (aka ifte, aka soft-cut, aka logical conditional) mif (mif c t' e') t e = mif c (\x - mif (t' x) t e) (mif e' t e) You're right of course: mode matters for the predicates that involve negation, such as mif. However, I believe that the mode is orthogonal to the

Re: [Haskell-cafe] Re: Lists vs. Monads

2005-07-21 Thread oleg
Jonathan Cast wrote: ] You can't define most initial models without recursive (or ] inductive) data types in general, because initial models are defined ] inductively. ] You can't define head, tail, or foldr using the MonadPlus ] signature ] OK. Right. I forgot about the Church

[Haskell-cafe] Control.Monad.Cont fun

2005-07-25 Thread oleg
On Thu, Jul 07, 2005 at 07:08:23PM +0200, Tomasz Zielonka wrote: Some time ago I wanted to return the escape continuation out of the callCC block, like this: getCC = callCC (\c - return c) It seems using shift/reset is better not only in principle but in practice as well. module Foo

  1   2   3   4   5   >