Re: [Haskell-cafe] Help to write type-level function

[Dmitry Kulagin]

That seems to be very relevant to my problem (especially HList.Record).
Am I right that UndecidableInstances is required mostly because of eq on
types, like in this instances:


class HRLabelSet (ps :: [*])
instance HRLabelSet '[]
instance HRLabelSet '[x]

instance ( HEq l1 l2 leq
 , HRLabelSet' l1 l2 leq r
 ) = HRLabelSet (LVPair l1 v1 ': LVPair l2 v2 ': r)

so the usage of the extension is unavoidable for my purposes?

Thank you!


On Wed, Feb 27, 2013 at 12:28 PM, o...@okmij.org wrote:


 Dmitry Kulagin wrote:
  I try to implement typed C-like structures in my little dsl.

 HList essentially had those
 http://code.haskell.org/HList/

  I was unable to implement required type function:
  type family Find (s :: Symbol) (xs :: [(Symbol,Ty)]) :: Ty
  Which just finds a type in a associative list.

 HList also implemented records with named fields. Indeed, you need a
 type-level lookup in an associative list, and for that you need type
 equality. (The ordinary List.lookup has the Eq constraint, doesn't
 it?)

 Type equality can be implemented with type functions, right now.
 http://okmij.org/ftp/Haskell/typeEQ.html#TTypeable

 (That page also defined a type-level list membership function).






___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Help to write type-level function

[Dmitry Kulagin]

Very clear solution, I will try to adopt it.

Thank you!


On Wed, Feb 27, 2013 at 12:17 PM, Aleksey Khudyakov 
alexey.sklad...@gmail.com wrote:

 On 27 February 2013 12:01, Raphael Gaschignard dasur...@gmail.com wrote:
  I think it might be impossible with type families. I don't think it's
  possible to differentiate with type families something like T a a, and T
 a
  b, with b different from a.
 
 It's indeed impossible to write such type function using type
 families. It will be possible with new closed type familes (they are
 in GHC head already).

 But for now it's possible to use overlapping instances and fundeps.
 Implementation of type level equality is simple and it's only
 instances which need ovelap.

 -- | Type class for type equality.
 class  TypeEq (a :: α) (b :: α) (eq :: Bool) | a b - eq
 instance   TypeEq a a True
 instance eq ~ False = TypeEq a b eq


 Implementation of lookup by key is relatively straightforward. Note
 that it doesn't check that key is unique.

 data k : v
 infix 6 :

 -- | Lookup type for given key
 class TyLookup (map :: [*]) (k :: *) (v :: *) | map k - v where

 class TyLookupCase (map :: [*]) (k :: *) (v :: *) (eq :: Bool) | map k
 eq - v where

 instance ( TypeEq k k' eq
  , TyLookupCase (k : v ': xs) k' v' eq
  ) = TyLookup  (k : v ': xs) k' v' where

 instance TyLookupCase (k  : v  ': xs) k v True  where
 instance TyLookup xs k v = TyLookupCase (k' : v' ': xs) k v False where

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Help to write type-level function

[Dmitry Kulagin]

Hi Aleksey,

Unfortunately, your solution does not work for me (ghc 7.6.2). I reduced
the problem to:

-- | Type class for type equality.
class  TypeEq (a :: α) (b :: α) (eq :: Bool) | a b - eq
instance   TypeEq a a True
-- instance TypeEq a b False
instance eq ~ False = TypeEq a b eq

f :: TypeEq Int Int True = Int
f = 1

When I try to invoke f, I get overlapping instances error:
Overlapping instances for TypeEq * Int Int 'True
  arising from a use of `f'
Matching instances:
  instance TypeEq k a a 'True -- Defined at Test.hs:14:24
  instance eq ~ 'False = TypeEq k a b eq -- Defined at Test.hs:16:10

Thanks.


On Wed, Feb 27, 2013 at 12:17 PM, Aleksey Khudyakov 
alexey.sklad...@gmail.com wrote:

 On 27 February 2013 12:01, Raphael Gaschignard dasur...@gmail.com wrote:
  I think it might be impossible with type families. I don't think it's
  possible to differentiate with type families something like T a a, and T
 a
  b, with b different from a.
 
 It's indeed impossible to write such type function using type
 families. It will be possible with new closed type familes (they are
 in GHC head already).

 But for now it's possible to use overlapping instances and fundeps.
 Implementation of type level equality is simple and it's only
 instances which need ovelap.

 -- | Type class for type equality.
 class  TypeEq (a :: α) (b :: α) (eq :: Bool) | a b - eq
 instance   TypeEq a a True
 instance eq ~ False = TypeEq a b eq


 Implementation of lookup by key is relatively straightforward. Note
 that it doesn't check that key is unique.

 data k : v
 infix 6 :

 -- | Lookup type for given key
 class TyLookup (map :: [*]) (k :: *) (v :: *) | map k - v where

 class TyLookupCase (map :: [*]) (k :: *) (v :: *) (eq :: Bool) | map k
 eq - v where

 instance ( TypeEq k k' eq
  , TyLookupCase (k : v ': xs) k' v' eq
  ) = TyLookup  (k : v ': xs) k' v' where

 instance TyLookupCase (k  : v  ': xs) k v True  where
 instance TyLookup xs k v = TyLookupCase (k' : v' ': xs) k v False where

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Help to write type-level function

[Dmitry Kulagin]

Oh, that is my fault - I was sure that I specified the extension and it
didn't help.
It really works with OverlappingUndecidable.
Thank you!


On Wed, Feb 27, 2013 at 10:36 PM, Aleksey Khudyakov 
alexey.sklad...@gmail.com wrote:

 On 27.02.2013 17:35, Dmitry Kulagin wrote:

 Hi Aleksey,

 Unfortunately, your solution does not work for me (ghc 7.6.2). I reduced
 the problem to:

 -- | Type class for type equality.
 class  TypeEq (a :: α) (b :: α) (eq :: Bool) | a b - eq
 instance   TypeEq a a True
 -- instance TypeEq a b False
 instance eq ~ False = TypeEq a b eq

  You need to add pragma {-# LANGUAGE OverlappingInstances #-}
 to the file where instances defined. Without it GHC will complain
 about overlap and unlike other extensions won't recommend pragma

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Help to write type-level function

[Dmitry Kulagin]

Hi,

I try to implement typed C-like structures in my little dsl.
I was able to express structures using type-level naturals (type Ty is
promoted):

 data Ty = TInt | TBool | TStruct Symbol [Ty]

That allowed to implement all needed functions, including type-level
function:

 type family Get (n :: Nat) (xs :: [Ty]) :: Ty

But it is not very convenient to identify struct's fields using naturals,
and I wanted to change Ty definition to:

 data Ty = TInt | TBool | TStruct Symbol [(Symbol, Ty)]

It is much closer to how C-struct looks, but I was unable to implement
required type function:

 type family Find (s :: Symbol) (xs :: [(Symbol,Ty)]) :: Ty

Which just finds a type in a associative list.

Could someone give me a hint, how to do it?
Or perhaps, is it just impossible thing to do?

Thanks!
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] why GHC cannot infer type in this case?

[Dmitry Kulagin]

That is great! I worked through the paper and played a lot with your code -
I must admit that I like this approach much more. I even added to my DSL
user-defined types in a type safe way, that I could not do with original
GADT-based design.

Thank you!
Dmitry


On Fri, Feb 1, 2013 at 12:09 PM, o...@okmij.org wrote:


 Dmitry Kulagin wrote:
  I try to implement little typed DSL with functions, but there is a
 problem:
  compiler is unable to infer type for my functions.

 One way to avoid the problem is to start with the tagless final
 representation. It imposes fewer requirements on the type system, and
 is a quite mechanical way of embedding DSL. The enclosed code
 re-implements your example in the tagless final style. If later you
 must have a GADT representation, one can easily write an interpreter
 that interprets your terms as GADTs (this is mechanical). For more
 examples, see the (relatively recent) lecture notes

 http://okmij.org/ftp/tagless-final/course/lecture.pdf

 {-# LANGUAGE TypeOperators, KindSignatures, DataKinds #-}
 {-# LANGUAGE NoMonomorphismRestriction, TypeFamilies #-}
 module TestExp where

 -- types of DSL terms
 data Ty = Int16 | TFun [Ty] Ty | TSeq [Ty]

 -- DSL terms
 class Exp (repr :: Ty - *) where
 int16:: Int - repr Int16
 add  :: repr Int16 - repr Int16 - repr Int16

 decl :: (repr (TSeq ts) - repr t) - repr (TFun ts t)
 call :: repr (TFun ts t) - repr (TSeq ts) - repr t

 -- building and deconstructing sequences
 unit :: repr (TSeq '[])
 cons :: repr t - repr (TSeq ts) - repr (TSeq (t ': ts))
 deco :: (repr t - repr (TSeq ts) - repr w) - repr (TSeq (t ': ts))
 - repr w

 -- A few convenience functions
 deun :: repr (TSeq '[]) - repr w - repr w
 deun _ x = x

 singleton :: Exp repr = (repr t - repr w) - repr (TSeq '[t]) - repr w
 singleton body = deco (\x _ - body x)

 -- sample terms
 fun =  decl $ singleton (\x - add (int16 2) x)
 -- Inferred type
 -- fun :: Exp repr = repr (TFun ((:) Ty 'Int16 ([] Ty)) 'Int16)

 test = call fun (cons (int16 3) unit)
 -- Inferred type
 -- test :: Exp repr = repr 'Int16

 fun2 =  decl $ deco (\x - singleton (\y - add (int16 2) (add x y)))
 {- inferred
 fun2
   :: Exp repr =
  repr (TFun ((:) Ty 'Int16 ((:) Ty 'Int16 ([] Ty))) 'Int16)
 -}

 test2 = call fun2 (int16 3 `cons` (int16 4 `cons` unit))



 -- Simple evaluator

 -- Interpret the object type Ty as Haskell type *
 type family TInterp (t :: Ty) :: *
 type instance TInterp Int16 = Int
 type instance TInterp (TFun ts t) = TISeq ts - TInterp t
 type instance TInterp (TSeq ts)   = TISeq ts

 type family TISeq (t :: [Ty]) :: *
 type instance TISeq '[]   = ()
 type instance TISeq (t1 ': ts) = (TInterp t1, TISeq ts)

 newtype R t = R{unR:: TInterp t}

 instance Exp R where
 int16 = R
 add (R x) (R y) = R $ x + y

 decl f = R $ \args - unR . f . R $ args
 call (R f) (R args) = R $ f args

 unit = R ()
 cons (R x) (R y) = R (x,y)
 deco f (R (x,y)) = f (R x) (R y)


 testv = unR test
 -- 5

 tes2tv = unR test2
 -- 9



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] why GHC cannot infer type in this case?

[Dmitry Kulagin]

Hi Cafe,

I try to implement little typed DSL with functions, but there is a problem:
compiler is unable to infer type for my functions. It seems that context
is clear, but still GHC complains Could not deduce
It is sad because without type inference the DSL will be very difficult to
use.
Could someone explain me why this happens and how it can be avoided?

I use GHC 7.4.2
I tried to distill the code to show the problem (and full error message
below it).

Thank you!
Dmitry

{-# LANGUAGE GADTs, KindSignatures, DataKinds #-}
module TestExp where

-- Sequence of DSL's types to represent type of tuple
data TSeq where
  TSeqEmpty :: TSeq
  TSeqCons :: TypeExp - TSeq - TSeq

-- All types allowed in DSL
data TypeExp where
  -- Primitive type
  TInt16 :: TypeExp
  -- Function type is built from types of arguments (TSeq) and type of
result
  TFun :: TSeq - TypeExp - TypeExp

-- Sequence of expressions to represent tuple
data Seq (t :: TSeq) where
  SeqEmpty :: Seq TSeqEmpty
  SeqCons :: Exp w - Seq v - Seq (TSeqCons w v)

data Exp (r :: TypeExp) where
  Decl :: (Seq args - Exp r) - Exp (TFun args r)
  Call :: Exp (TFun args r) - Seq args - Exp r
  Int16 :: Int - Exp TInt16
  Add :: Exp TInt16 - Exp TInt16 - Exp TInt16

-- Assumed semantics: fun x = x + 2
-- The following line must be uncommented to compile without errors
-- fun :: Exp (TFun (TSeqCons TInt16 TSeqEmpty) TInt16)
fun = Decl $ \(SeqCons x SeqEmpty) - Add (Int16 2) x


-- eval (Int16 x) = x
-- eval (Call (Decl f) seq) = eval (f seq)
-- eval (Add x y) = eval x + eval y

-- test = eval $ Call fun (SeqCons (Int16 3) SeqEmpty)

- There is full error message: 
TestExp.hs:30:53:
Could not deduce (w ~ 'TInt16)
from the context (args ~ TSeqCons w v)
  bound by a pattern with constructor
 SeqCons :: forall (w :: TypeExp) (v :: TSeq).
Exp w - Seq v - Seq (TSeqCons w v),
   in a lambda abstraction
  at TestExp.hs:30:16-33
or from (v ~ 'TSeqEmpty)
  bound by a pattern with constructor
 SeqEmpty :: Seq 'TSeqEmpty,
   in a lambda abstraction
  at TestExp.hs:30:26-33
  `w' is a rigid type variable bound by
  a pattern with constructor
SeqCons :: forall (w :: TypeExp) (v :: TSeq).
   Exp w - Seq v - Seq (TSeqCons w v),
  in a lambda abstraction
  at TestExp.hs:30:16
Expected type: Exp 'TInt16
  Actual type: Exp w
In the second argument of `Add', namely `x'
In the expression: Add (Int16 2) x
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] why GHC cannot infer type in this case?

[Dmitry Kulagin]

Andres, thank you!

Your response is really helpful. I will try to adopt your suggestion.

Thank again!
Dmitry


On Thu, Jan 31, 2013 at 7:27 PM, Andres Löh and...@well-typed.com wrote:

 Hi Dmitry.

  I try to implement little typed DSL with functions, but there is a
 problem:
  compiler is unable to infer type for my functions. It seems that
 context
  is clear, but still GHC complains Could not deduce
  It is sad because without type inference the DSL will be very difficult
 to
  use.
 
  Could someone explain me why this happens and how it can be avoided?

 Pattern matches on GADT generally require type information. Type
 inference in such a case is tricky. GADTs are so powerful that in many
 cases, there's no unique best type to infer.

 As a contrived example, consider this datatype and function:

  data X :: * - * where
 C :: Int - X Int
 D :: X a
 
  f (C n) = [n]
  f D = []

 What should GHC infer for f? Both

  f :: X a - [Int]
  f :: X a - [a]

 are reasonable choices, but without further information about the
 context, it's impossible to say which one of the two is better.

 It is theoretically possible to be more clever than GHC is and infer
 the types of GADT pattern matches in some cases. However, it is (A) a
 lot of work to implement and maintain that cleverness, and (B) it is
 then very difficult to describe when exactly a type signature is
 required and when it isn't. So GHC adopts the simpler approach and
 requires type information for all GADT pattern matches, which is a
 simple and predictable rule.

 How to prevent such errors in general is difficult to say. In your
 particular case, there might be an option, though. If you additionally
 use TypeFamilies and FlexibleInstances, you can define:

  class MkDecl d where
type MkDeclSeq d :: TSeq
type MkDeclRes d :: TypeExp
decl' :: d - Seq (MkDeclSeq d) - Exp (MkDeclRes d)
 
  instance MkDecl (Exp r) where
type MkDeclSeq (Exp r) = TSeqEmpty
type MkDeclRes (Exp r) = r
decl' e = \ SeqEmpty - e
 
  instance MkDecl d = MkDecl (Exp w - d) where
type MkDeclSeq (Exp w - d) = TSeqCons w (MkDeclSeq d)
type MkDeclRes (Exp w - d) = MkDeclRes d
decl' f = \ (SeqCons x xs) - decl' (f x) xs
 
  decl :: MkDecl d = d - Exp (TFun (MkDeclSeq d) (MkDeclRes d))
  decl d = Decl (decl' d)
 
  fun = decl $ \ x - Add (Int16 2) x

 The idea here is to avoid pattern matching on the GADT, and instead
 use an ordinary Haskell function as an argument to the decl smart
 constructor. We use the type class and two type families to pack that
 function (with as many arguments as it has) into the type-level list
 and wrap it all up in the original Decl. This works because on the
 outside, no GADT pattern matches are involved, and within the type
 class instances, the necessary type information is present.

 This is certainly harder to understand than your original version. On
 the other hand, it's actually easier to use.

 (It's entirely possible that my code can be simplified further. I
 haven't thought about this for very long ...)

 Cheers,
   Andres

 --
 Andres Löh, Haskell Consultant
 Well-Typed LLP, http://www.well-typed.com

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] containers license issue

[Dmitry Kulagin]

Hi Cafe,

I am faced with unpleasant problem. The lawyer of my company checked
sources of containers package and found out that it refers to some
GPL-library.

Here is quote:
The algorithm is derived from Jorg Arndt's FXT library
in file Data/IntMap/Base.hs

The problem is that FXT library is GPL and thus containers package can not
be considered as BSD3. And it means that it can not be used in my case
(closed source software).

Is this logic actually correct and containers should be considered as GPL?

The package is widely used by other packages and the only way I see right
now is to fix sources to reimplement this functionality, which is not good
option.

Thank you!
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] containers license issue

[Dmitry Kulagin]

Clark, Johan, thank you! That looks like perfect solution to the problem.

12.12.2012, в 22:56, Johan Tibell johan.tib...@gmail.com написал(а):

 On Wed, Dec 12, 2012 at 10:40 AM, Clark Gaebel cgae...@uwaterloo.ca wrote:
 I just did a quick derivation from
 http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 to get
 the highest bit mask, and did not reference FXT nor the containers
 implementation. Here is my code:

 highestBitMask :: Word64 - Word64
 highestBitMask x1 = let x2 = x1 .|. x1 `shiftR` 1
x3 = x2 .|. x2 `shiftR` 2
x4 = x3 .|. x3 `shiftR` 4
x5 = x4 .|. x4 `shiftR` 8
x6 = x5 .|. x5 `shiftR` 16
x7 = x6 .|. x6 `shiftR` 32
 in x7 `xor` (x7 `shiftR` 1)

 This code is hereby released into the public domain. Problem solved.

 I will integrate this into containers later today.

 ___
 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] Can not use ST monad with polymorphic function

[Dmitry Kulagin]

 Basically, quantified types can't be given as arguments to type
 constructors (other than -, which is its own thing). I'm not entirely
 sure
 why, but it apparently makes the type system very complicated from a
 theoretical standpoint. By wrapping the quantified type in a newtype, the
 argument to IO becomes simple enough not to cause problems.


Thank you, I have read about predicative types and it seems I understand
the origin of the problem now.


  GHC has an extension -XImpredicativeTypes that lifts this restriction,
 but in my experience, it doesn't work very well.


Yes, it didn't help in my case.

Thank you,
Dmitry
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Can not use ST monad with polymorphic function

[Dmitry Kulagin]

Thank you, MigMit!

If I replace your type FoldSTVoid with:
data FoldMVoid = FoldMVoid {runFold :: Monad m = (Int - m ()) - m ()}

then everything works magically with any monad!
That is exactly what I wanted, though I still do not quite understand why
wrapping the type solves the problem

Dmitry


On Thu, Nov 29, 2012 at 12:01 AM, MigMit miguelim...@yandex.ru wrote:

 Yes, monomorphism. do binding requires your fold'' to be of some
 monomorphic type, but runST requires some polymorphism.

 If you want, you can use special type like that:

 data FoldSTVoid = FoldSTVoid {runFold :: forall a. (Int - ST a ()) - ST
 a ()}

 fold :: Monad m = (Int - m ()) - m ()
 fold f = mapM_ f [0..20]

 selectFold :: String - IO FoldSTVoid -- ((Int - m ()) - m ())
 selectFold method = do
 -- in real program I'd like to choose between
 -- different fold methods, based on some IO context
 return $ FoldSTVoid fold

 useFold :: FoldSTVoid - ST a ()
 useFold fold' = runFold fold' f
 where f _ = return () -- some trivial iterator

 main = do
 fold'' - selectFold some-method-id
 print $ runST $ useFold fold''

 On Nov 28, 2012, at 9:52 PM, Dmitry Kulagin dmitry.kula...@gmail.com
 wrote:

  Hi Cafe,
 
  I try to implement some sort of monadic fold, where traversing is
 polymorphic over monad type.
  The problem is that the code below does not compile. It works with any
 monad except for ST.
  I suspect that monomorphism is at work here, but it is unclear for me
 how to change the code to make it work with ST.
 
  fold :: Monad m = (Int - m ()) - m ()
  fold f = mapM_ f [0..20]
 
  selectFold :: Monad m = String - IO ((Int - m ()) - m ())
  selectFold method = do
  -- in real program I'd like to choose between
  -- different fold methods, based on some IO context
  return fold
 
  useFold :: Monad m = ((Int - m ()) - m ()) - m ()
  useFold fold' = fold' f
  where f _ = return () -- some trivial iterator
 
  main = do
  fold'' - selectFold some-method-id
  print $ runST $ useFold fold''
 
 
  Thank you!
  Dmitry
  ___
  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] Can not use ST monad with polymorphic function

[Dmitry Kulagin]

Hi Cafe,

I try to implement some sort of monadic fold, where traversing is
polymorphic over monad type.
The problem is that the code below does not compile. It works with any
monad except for ST.
I suspect that monomorphism is at work here, but it is unclear for me how
to change the code to make it work with ST.

fold :: Monad m = (Int - m ()) - m ()
fold f = mapM_ f [0..20]

selectFold :: Monad m = String - IO ((Int - m ()) - m ())
selectFold method = do
-- in real program I'd like to choose between
-- different fold methods, based on some IO context
return fold

useFold :: Monad m = ((Int - m ()) - m ()) - m ()
useFold fold' = fold' f
where f _ = return () -- some trivial iterator

main = do
fold'' - selectFold some-method-id
print $ runST $ useFold fold''


Thank you!
Dmitry
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] More liberal than liberal type synonyms

[Dmitry Kulagin]

Hi Dan,

I am still pretty new in Haskell, but this problem annoys me already.

If I define certain monad as a type synonym:

type StateA a = StateT SomeState SomeMonad a

Then I can't declare new monad based on the synonym:

type StateB a = StateT SomeOtherState StateA a

The only way I know to overcome is to declare StateA without `a':

type StateA = StateT SomeState SomeMonad

But it is not always possible with existing code base.

I am sorry, if this is offtopic, but it seemed to me that the problem
is realted to partially applied type synomyms you described.

Thanks!
Dmitry

On Tue, Dec 6, 2011 at 10:59 PM, Dan Doel dan.d...@gmail.com wrote:
 Greetings,

 In the process of working on a Haskell-alike language recently, Ed
 Kmett and I realized that we had (without really thinking about it)
 implemented type synonyms that are a bit more liberal than GHC's. With
 LiberalTypeSynonyms enabled, GHC allows:

    type Foo a b = b - a
    type Bar f = f String Int

    baz :: Bar Foo
    baz = show

 because Bar expands to saturate Foo. However, we had also implemented
 the following, which fails in GHC:

    type Foo a b = b - a
    type Bar f = f (Foo Int) (Foo Int)
    type Baz f g = f Int - g Int

    quux :: Bar Baz
    quux = id

 That is: type synonyms are allowed to be partially applied within
 other type synonyms, as long as similar transitive saturation
 guarantees are met during their use.

 I don't know how useful it is, but I was curious if anyone can see
 anything wrong with allowing this (it seems okay to me after a little
 thought), and thought I'd float the idea out to the GHC developers, in
 case they're interested in picking it up.

 -- Dan

 ___
 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] More liberal than liberal type synonyms

[Dmitry Kulagin]

 You should be able to write something like this:

 type StateB a b = StateT SomeOtherState (StateA a) b

Thank you for reply, but this variant actually does not compile:
StateA and (StateA a) have different kinds.

Dmitry


 Best regards, Øystein Kolsrud


 On Wed, Dec 7, 2011 at 11:48 AM, Dmitry Kulagin dmitry.kula...@gmail.com
 wrote:

 Hi Dan,

 I am still pretty new in Haskell, but this problem annoys me already.

 If I define certain monad as a type synonym:

    type StateA a = StateT SomeState SomeMonad a

 Then I can't declare new monad based on the synonym:

    type StateB a = StateT SomeOtherState StateA a

 The only way I know to overcome is to declare StateA without `a':

    type StateA = StateT SomeState SomeMonad

 But it is not always possible with existing code base.

 I am sorry, if this is offtopic, but it seemed to me that the problem
 is realted to partially applied type synomyms you described.

 Thanks!
 Dmitry

 On Tue, Dec 6, 2011 at 10:59 PM, Dan Doel dan.d...@gmail.com wrote:
  Greetings,
 
  In the process of working on a Haskell-alike language recently, Ed
  Kmett and I realized that we had (without really thinking about it)
  implemented type synonyms that are a bit more liberal than GHC's. With
  LiberalTypeSynonyms enabled, GHC allows:
 
     type Foo a b = b - a
     type Bar f = f String Int
 
     baz :: Bar Foo
     baz = show
 
  because Bar expands to saturate Foo. However, we had also implemented
  the following, which fails in GHC:
 
     type Foo a b = b - a
     type Bar f = f (Foo Int) (Foo Int)
     type Baz f g = f Int - g Int
 
     quux :: Bar Baz
     quux = id
 
  That is: type synonyms are allowed to be partially applied within
  other type synonyms, as long as similar transitive saturation
  guarantees are met during their use.
 
  I don't know how useful it is, but I was curious if anyone can see
  anything wrong with allowing this (it seems okay to me after a little
  thought), and thought I'd float the idea out to the GHC developers, in
  case they're interested in picking it up.
 
  -- Dan
 
  ___
  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




 --
 Mvh Øystein Kolsrud

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] More liberal than liberal type synonyms

[Dmitry Kulagin]

 Dmitry, does your code work with LiberalTypeSynonyms extention activated?
No, the same error:
Type synonym `StateA' should have 1 argument, but has been given 0

But I have GHC 6.12.3

Dmitry
2011/12/7 Yves Parès limestr...@gmail.com:
 This is impossible:
 in the definition of 'StateT s m a', m must be a monad and then have the *
 - * kind.
 So you cannot pass (StateA a), because it has simply the * kind.

 Dmitry, does your code work with LiberalTypeSynonyms extention activated?


 2011/12/7 Øystein Kolsrud kols...@gmail.com

 You should be able to write something like this:

 type StateB a b = StateT SomeOtherState (StateA a) b

 Best regards, Øystein Kolsrud


 On Wed, Dec 7, 2011 at 11:48 AM, Dmitry Kulagin dmitry.kula...@gmail.com
 wrote:

 Hi Dan,

 I am still pretty new in Haskell, but this problem annoys me already.

 If I define certain monad as a type synonym:

    type StateA a = StateT SomeState SomeMonad a

 Then I can't declare new monad based on the synonym:

    type StateB a = StateT SomeOtherState StateA a

 The only way I know to overcome is to declare StateA without `a':

    type StateA = StateT SomeState SomeMonad

 But it is not always possible with existing code base.

 I am sorry, if this is offtopic, but it seemed to me that the problem
 is realted to partially applied type synomyms you described.

 Thanks!
 Dmitry

 On Tue, Dec 6, 2011 at 10:59 PM, Dan Doel dan.d...@gmail.com wrote:
  Greetings,
 
  In the process of working on a Haskell-alike language recently, Ed
  Kmett and I realized that we had (without really thinking about it)
  implemented type synonyms that are a bit more liberal than GHC's. With
  LiberalTypeSynonyms enabled, GHC allows:
 
     type Foo a b = b - a
     type Bar f = f String Int
 
     baz :: Bar Foo
     baz = show
 
  because Bar expands to saturate Foo. However, we had also implemented
  the following, which fails in GHC:
 
     type Foo a b = b - a
     type Bar f = f (Foo Int) (Foo Int)
     type Baz f g = f Int - g Int
 
     quux :: Bar Baz
     quux = id
 
  That is: type synonyms are allowed to be partially applied within
  other type synonyms, as long as similar transitive saturation
  guarantees are met during their use.
 
  I don't know how useful it is, but I was curious if anyone can see
  anything wrong with allowing this (it seems okay to me after a little
  thought), and thought I'd float the idea out to the GHC developers, in
  case they're interested in picking it up.
 
  -- Dan
 
  ___
  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




 --
 Mvh Øystein Kolsrud

 ___
 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] More liberal than liberal type synonyms

[Dmitry Kulagin]

 For short, type synonyms work for mere aliases, but not for full-fledged 
 type-level non-inductive functions. And sometimes we intuitively want to use 
 them as such.
Thank you, Yves! It is now more clear for me.

Still, it seems that ability to use partially applied type synonyms would be
very natural (and useful) extension to the language. It would allow to avoid
boilerplate code associated with creating really new types instead of just
using synonims for existing ones.

On Wed, Dec 7, 2011 at 3:51 PM, Yves Parès limestr...@gmail.com wrote:
 Ah, maybe Dan could tell us if it works only with GHC 7.

 Dmitry, I had your problem many times. The last time was when I saw you
 could define the ContT monad in terms of Cont (the opposite is done in the
 mtl).
 It leads to a simpler code, but you are stucked when trying to define ContT
 as an instance of MonadTrans:

 data Cont r a = ...
 -- [instances of Monad Cont, blah blah blah]

 type ContT r m a = Cont r (m a)

 instance MonadTrans (ContT r) where  -- This doesn't compile, even if it is
 logical
   lift = ...

 For short, type synonyms work for mere aliases, but not for full-fledged
 type-level non-inductive functions.
 And sometimes we intuitively want to use them as such.


 2011/12/7 Dmitry Kulagin dmitry.kula...@gmail.com

  Dmitry, does your code work with LiberalTypeSynonyms extention
  activated?
 No, the same error:
 Type synonym `StateA' should have 1 argument, but has been given 0

 But I have GHC 6.12.3

 Dmitry
 2011/12/7 Yves Parès limestr...@gmail.com:
  This is impossible:
  in the definition of 'StateT s m a', m must be a monad and then have the
  *
  - * kind.
  So you cannot pass (StateA a), because it has simply the * kind.
 
  Dmitry, does your code work with LiberalTypeSynonyms extention
  activated?
 
 
  2011/12/7 Øystein Kolsrud kols...@gmail.com
 
  You should be able to write something like this:
 
  type StateB a b = StateT SomeOtherState (StateA a) b
 
  Best regards, Øystein Kolsrud
 
 
  On Wed, Dec 7, 2011 at 11:48 AM, Dmitry Kulagin
  dmitry.kula...@gmail.com
  wrote:
 
  Hi Dan,
 
  I am still pretty new in Haskell, but this problem annoys me already.
 
  If I define certain monad as a type synonym:
 
     type StateA a = StateT SomeState SomeMonad a
 
  Then I can't declare new monad based on the synonym:
 
     type StateB a = StateT SomeOtherState StateA a
 
  The only way I know to overcome is to declare StateA without `a':
 
     type StateA = StateT SomeState SomeMonad
 
  But it is not always possible with existing code base.
 
  I am sorry, if this is offtopic, but it seemed to me that the problem
  is realted to partially applied type synomyms you described.
 
  Thanks!
  Dmitry
 
  On Tue, Dec 6, 2011 at 10:59 PM, Dan Doel dan.d...@gmail.com wrote:
   Greetings,
  
   In the process of working on a Haskell-alike language recently, Ed
   Kmett and I realized that we had (without really thinking about it)
   implemented type synonyms that are a bit more liberal than GHC's.
   With
   LiberalTypeSynonyms enabled, GHC allows:
  
      type Foo a b = b - a
      type Bar f = f String Int
  
      baz :: Bar Foo
      baz = show
  
   because Bar expands to saturate Foo. However, we had also
   implemented
   the following, which fails in GHC:
  
      type Foo a b = b - a
      type Bar f = f (Foo Int) (Foo Int)
      type Baz f g = f Int - g Int
  
      quux :: Bar Baz
      quux = id
  
   That is: type synonyms are allowed to be partially applied within
   other type synonyms, as long as similar transitive saturation
   guarantees are met during their use.
  
   I don't know how useful it is, but I was curious if anyone can see
   anything wrong with allowing this (it seems okay to me after a
   little
   thought), and thought I'd float the idea out to the GHC developers,
   in
   case they're interested in picking it up.
  
   -- Dan
  
   ___
   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
 
 
 
 
  --
  Mvh Øystein Kolsrud
 
  ___
  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] Out of memory if compiled with -O2, why?

[Dmitry Kulagin]

Thank you, it is indeed very similar problem.
Nevertheless it seems that the lst function is not the direct reason, because:
1) if I inline lst (by hands), the problem is still there
2) size of the list is actially not so large - just 15 millions elements

I am almost sure that the reason is Map.fromList - result of the
function perhaps somehow memoized and not released by GC.

Dmitry.

On Wed, Dec 1, 2010 at 8:15 PM, Petr Prokhorenkov
prokhoren...@gmail.com wrote:
 Hi, Dmitry

 I recently had the same problem:
 http://www.haskell.org/pipermail/haskell-cafe/2010-November/086450.html

 Memory is taken by the list returned by your lst function wich is
 being shared across g,h,i,j,k,l,m,n.
 Apparently there is no safe and easy way to overcome this yet :(

 --
 Regards,
 Petr



 On Wed, Dec 1, 2010 at 5:23 PM, Dmitry Kulagin dmitry.kula...@gmail.com 
 wrote:
 Hi,

 I have problems with memory leaks and can't find out how to avoid them.
 I tried to reduce sample to demonstrate the following problems:
 1) when compiled without -O2 option, it iconsumes 1582MB (!) total memory
 2) when compiled with -O2 option it terminates with out of memory

 Actually I don't understand the reasons, particulary why  GC can't
 collect already processed objects g,...,n (see code below)?

 I would appreciate very much any help with this situation.
 Thanks!


 module Main where

 import qualified Data.Map as M

 len = 15*1024*1024
 lst from = take len $ zip [from..] [0..]

 g = M.size $ M.fromList $ lst 0
 h = M.size $ M.fromList $ lst 0
 i = M.size $ M.fromList $ lst 0
 j = M.size $ M.fromList $ lst 0
 k = M.size $ M.fromList $ lst 0
 l = M.size $ M.fromList $ lst 0
 m = M.size $ M.fromList $ lst 0
 n = M.size $ M.fromList $ lst 0

 main = do
    mapM_ print [g,h,i,j,k,l,m,n]

 ___
 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] Out of memory if compiled with -O2, why?

[Dmitry Kulagin]

Hi,

I have problems with memory leaks and can't find out how to avoid them.
I tried to reduce sample to demonstrate the following problems:
1) when compiled without -O2 option, it iconsumes 1582MB (!) total memory
2) when compiled with -O2 option it terminates with out of memory

Actually I don't understand the reasons, particulary why  GC can't
collect already processed objects g,...,n (see code below)?

I would appreciate very much any help with this situation.
Thanks!


module Main where

import qualified Data.Map as M

len = 15*1024*1024
lst from = take len $ zip [from..] [0..]

g = M.size $ M.fromList $ lst 0
h = M.size $ M.fromList $ lst 0
i = M.size $ M.fromList $ lst 0
j = M.size $ M.fromList $ lst 0
k = M.size $ M.fromList $ lst 0
l = M.size $ M.fromList $ lst 0
m = M.size $ M.fromList $ lst 0
n = M.size $ M.fromList $ lst 0

main = do
mapM_ print [g,h,i,j,k,l,m,n]

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe