[Haskell-cafe] abs minBound (0 :: Int) negate minBound == (minBound :: Int)
The docs at http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:gcd give a NB mentioning that (abs minBound == minBound) is possible for fixed-width types. This holds, for example, at Int. It is also the case that (negate minBound == minBound). Two questions: 1) This behavior surprised me. Does it surprise enough people to include a warning in the Haddock for abs and negate? IE Here. http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Num 2) Is this a common behavior in other languages? My tinkering with gcc suggests it does not support the value -2^63, but instead bottoms out at (-2^63+1). Thanks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Template Haskell sometimes sees hidden constructors
A quick follow-up:
1) I had a typo: it should say N4 is like N1 with a phantom type variable.
2) In my larger code base, the constructor that is visible to TH when
I think it shouldn't be is part of a type that is alpha-equivalent to
N3. It's odd that N3 doesn't exhibit the leakiness here but an
alpha-equivalent type does exhibit it in my larger program.
On Fri, May 27, 2011 at 12:04 PM, Nicolas Frisby
nicolas.fri...@gmail.com wrote:
With the three modules at the end of this email, I get some
interesting results. Note that none of the constructors are exported,
yet Template Haskell can see (and splice in variable occurrences of!)
T, C2, W1, and W4.
If you load Dump into GHCi, you get to see the Info that TH provides
when you reify each of the data types. For T, T2, N1, and N4, their
construct is visible in the Info even though M doesn't export it.
As a consequence, you can load Unhide with no errors. Thus c = C, c2 =
C2, w1 = N1, and w4 = N4, even though those constructors were not
supposed to be imported.
I couldn't find any mention of this on the GHC Trac for Template
Haskell or for a general search of reify.
* http://j.mp/l9Ztjz (Description contains reify)
* http://j.mp/mprUmq (Component = Template Haskell)
* Disclaimer: I didn't take the time to inspect this one
http://hackage.haskell.org/trac/ghc/ticket/4946
T is isomorphic to (), T2 is like T with a phantom type argument, N1
is a newtype wrapping an Int, and N4 is like N3 with a phantom type
variable. This seems too inconsistent to be an intended behavior. Am I
missing something? Thanks.
== M.hs ==
module M (T(), T1(), T2(), T3(), T4(), N1(), N3(), N4()) where
data T = C
data T1 = C1 Int
data T2 a = C2
data T3 a = C3 a
data T4 a = C4 Int
newtype N1 = W1 Int
newtype N3 a = W3 a
newtype N4 a = W4 Int
== Dump.hs ==
{-# LANGUAGE TemplateHaskell #-}
module Dump where
import Language.Haskell.TH
import M
dumpT, dumpT1, dumpT2, dumpT3, dumpT4, dumpN1, dumpN3, dumpN4 :: ()
dumpT = $(reify ''T = fail . show)
dumpT1 = $(reify ''T1 = fail . show)
dumpT2 = $(reify ''T2 = fail . show)
dumpT3 = $(reify ''T3 = fail . show)
dumpT4 = $(reify ''T4 = fail . show)
dumpN1 = $(reify ''N1 = fail . show)
dumpN3 = $(reify ''N3 = fail . show)
dumpN4 = $(reify ''N4 = fail . show)
== Unhide.hs ==
{-# LANGUAGE TemplateHaskell #-}
module Unhide where
import Language.Haskell.TH
import M
c :: T
c = $((\(TyConI (DataD _ _ _ [NormalC n _] _)) - ConE n) `fmap` reify ''T)
c2 :: T2 a
c2 = $((\(TyConI (DataD _ _ _ [NormalC n _] _)) - ConE n) `fmap` reify ''T2)
w1 :: Int - N1
w1 = $((\(TyConI (NewtypeD _ _ _ (NormalC n _) _)) - ConE n) `fmap` reify
''N1)
w4 :: Int - N4 a
w4 = $((\(TyConI (NewtypeD _ _ _ (NormalC n _) _)) - ConE n) `fmap` reify
''N4)
- for convenience, this is what I get when I load Dump in ghci
Dump.hs:9:11:
TyConI (DataD [] M.T [] [NormalC M.C []] [])
In the expression: $(reify 'T = fail . show)
In an equation for `dumpT': dumpT = $(reify 'T = fail . show)
Dump.hs:10:12:
TyConI (DataD [] M.T1 [] [] [])
In the expression: $(reify 'T1 = fail . show)
In an equation for `dumpT1': dumpT1 = $(reify 'T1 = fail . show)
Dump.hs:11:12:
TyConI (DataD [] M.T2 [PlainTV a_1627390697] [NormalC M.C2 []] [])
In the expression: $(reify 'T2 = fail . show)
In an equation for `dumpT2': dumpT2 = $(reify 'T2 = fail . show)
Dump.hs:12:12:
TyConI (DataD [] M.T3 [PlainTV a_1627390696] [] [])
In the expression: $(reify 'T3 = fail . show)
In an equation for `dumpT3': dumpT3 = $(reify 'T3 = fail . show)
Dump.hs:13:12:
TyConI (DataD [] M.T4 [PlainTV a_1627390695] [] [])
In the expression: $(reify 'T4 = fail . show)
In an equation for `dumpT4': dumpT4 = $(reify 'T4 = fail . show)
Dump.hs:14:12:
TyConI (NewtypeD [] M.N1 [] (NormalC M.W1 [(NotStrict,ConT
GHC.Types.Int)]) [])
In the expression: $(reify 'N1 = fail . show)
In an equation for `dumpN1': dumpN1 = $(reify 'N1 = fail . show)
Dump.hs:15:12:
TyConI (DataD [] M.N3 [PlainTV a_1627390694] [] [])
In the expression: $(reify 'N3 = fail . show)
In an equation for `dumpN3': dumpN3 = $(reify 'N3 = fail . show)
Dump.hs:16:12:
TyConI (NewtypeD [] M.N4 [PlainTV a_1627390693] (NormalC M.W4
[(NotStrict,ConT GHC.Types.Int)]) [])
In the expression: $(reify 'N4 = fail . show)
In an equation for `dumpN4': dumpN4 = $(reify 'N4 = fail . show)
Failed, modules loaded: M.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] something between a QQ and Q Exp?
This message motivates adding support to Template Haskell for code
that can be spliced but can no longer be intensionally analyzed.
I'm trying to use the well-known technique of a hidden constructor in
order to represent values that satisfy a particular predicate.
module Safe (Safe(), safe, mkSafe) where
newtype Safe a = Hidden a -- the Hidden constructor is not exported
safe :: Safe a - a-- the safe observer is exported
In my case, the predicate is a restriction on the Haskell syntax used
to define the value. In fact, in order to check my predicate, I need
some of the information that TH embeds in the result of a [| ... |]
quote. Thus I'm using TH to validate the construction of Safe values.
isSafe :: Exp - Bool
isSafe = ... -- uses TH metadata embedded in the Exp
mkSafe :: Q Exp - Q Exp
mkSafe m = do
e - m
if isSafe e
then return (AppE (ConE 'Hidden) e)
else fail (not safe:\n\t ++ pprint e)
A user's construction of a Safe value then looks like $(mkSafe [| ...
|]) in some other module. I'd like this to be the only way to build a
Safe value.
Unfortunately, TH is a double-edged sword. In particular, it can be
used to expose the Hidden constructor, thereby invalidating the Safe
type encapsulation of my invariant.
abuse (AppE con _) = con
uhoh :: a - Safe a
uhoh = $(liftM abuse (safe [| ... |]))
On the one hand, I need the user to use TH in order to construct Safe
values. On the other, abuse of TH is capable of breaking my security
kernel all together. If I could get by with a QuasiQuoter such as
[mkSafe| ... |], the Hidden constructor would indeed be safe since
the result of mkSafe is spliced in immediately and the user has no
further access to it. Unfortunately, QuasiQuoters don't have access to
the metadata that TH embeds in its quotations, which I need for
validation. This inspires my idea for a solution: something between
the two mechanisms.
My first thought for a solution involved a new core type for Template
Haskell. The Splice type would be completely abstract except for
constructing it from a splicable type and the ability to splice a
Splice into a program. So, TH could splice in either Q alpha like
normal or Q (Splice alpha), for alpha an element of {Exp, Pat, Type,
[Dec]}. mkSafe could be rewritten to generate a Splice instead of
just an Exp, and hence an abusive user could no longer snoop the
generated expression to extract the Hidden constructor. Unfortunately,
if Splice is just another newtype with a hidden constructor, then it
could be subverted in the same way that the abuse function exposes
the Hidden constructor. Without further support from the Template
Haskell system itself, it's turtles all the way down, I suspect.
The popularity and convenience of creating a safety kernel by hiding
constructors lends importance to plugging this hole, I think. Template
Haskell is a useful system, but it currently subverts the most common
lightweight approach to enforcing data invariants in the Haskell type
system. It'd be nice if both could be used in the same system --
especially since the user can invoke Template Haskell regardless of
the library author's intent.
Is there already a way to write a security kernel that is robust
against this sort of Template Haskell abuse? Or would we need further
support from the Template Haskell system?
Thanks for your time.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Template Haskell sometimes sees hidden constructors
Whith the three modules at the end of this email, I get some
interesting results. Note that none of the constructors are exported,
yet Template Haskell can see (and splice in variable occurrences of!)
T, C2, W1, and W4.
If you load Dump into GHCi, you get to see the Info that TH provides
when you reify each of the data types. For T, T2, N1, and N4, their
construct is visible in the Info even though M doesn't export it.
As a consequence, you can load Unhide with no errors. Thus c = C, c2 =
C2, w1 = N1, and w4 = N4, even though those constructors were not
supposed to be imported.
I couldn't find any mention of this on the GHC Trac for Template
Haskell or for a general search of reify.
* http://j.mp/l9Ztjz (Description contains reify)
* http://j.mp/mprUmq (Component = Template Haskell)
* Disclaimer: I didn't take the time to inspect this one
http://hackage.haskell.org/trac/ghc/ticket/4946
T is isomorphic to (), T2 is like T with a phantom type argument, N1
is a newtype wrapping an Int, and N4 is like N3 with a phantom type
variable. This seems too inconsistent to be an intended behavior. Am I
missing something? Thanks.
== M.hs ==
module M (T(), T1(), T2(), T3(), T4(), N1(), N3(), N4()) where
data T = C
data T1 = C1 Int
data T2 a = C2
data T3 a = C3 a
data T4 a = C4 Int
newtype N1 = W1 Int
newtype N3 a = W3 a
newtype N4 a = W4 Int
== Dump.hs ==
{-# LANGUAGE TemplateHaskell #-}
module Dump where
import Language.Haskell.TH
import M
dumpT, dumpT1, dumpT2, dumpT3, dumpT4, dumpN1, dumpN3, dumpN4 :: ()
dumpT = $(reify ''T = fail . show)
dumpT1 = $(reify ''T1 = fail . show)
dumpT2 = $(reify ''T2 = fail . show)
dumpT3 = $(reify ''T3 = fail . show)
dumpT4 = $(reify ''T4 = fail . show)
dumpN1 = $(reify ''N1 = fail . show)
dumpN3 = $(reify ''N3 = fail . show)
dumpN4 = $(reify ''N4 = fail . show)
== Unhide.hs ==
{-# LANGUAGE TemplateHaskell #-}
module Unhide where
import Language.Haskell.TH
import M
c :: T
c = $((\(TyConI (DataD _ _ _ [NormalC n _] _)) - ConE n) `fmap` reify ''T)
c2 :: T2 a
c2 = $((\(TyConI (DataD _ _ _ [NormalC n _] _)) - ConE n) `fmap` reify ''T2)
w1 :: Int - N1
w1 = $((\(TyConI (NewtypeD _ _ _ (NormalC n _) _)) - ConE n) `fmap` reify ''N1)
w4 :: Int - N4 a
w4 = $((\(TyConI (NewtypeD _ _ _ (NormalC n _) _)) - ConE n) `fmap` reify ''N4)
- for convenience, this is what I get when I load Dump in ghci
Dump.hs:9:11:
TyConI (DataD [] M.T [] [NormalC M.C []] [])
In the expression: $(reify 'T = fail . show)
In an equation for `dumpT': dumpT = $(reify 'T = fail . show)
Dump.hs:10:12:
TyConI (DataD [] M.T1 [] [] [])
In the expression: $(reify 'T1 = fail . show)
In an equation for `dumpT1': dumpT1 = $(reify 'T1 = fail . show)
Dump.hs:11:12:
TyConI (DataD [] M.T2 [PlainTV a_1627390697] [NormalC M.C2 []] [])
In the expression: $(reify 'T2 = fail . show)
In an equation for `dumpT2': dumpT2 = $(reify 'T2 = fail . show)
Dump.hs:12:12:
TyConI (DataD [] M.T3 [PlainTV a_1627390696] [] [])
In the expression: $(reify 'T3 = fail . show)
In an equation for `dumpT3': dumpT3 = $(reify 'T3 = fail . show)
Dump.hs:13:12:
TyConI (DataD [] M.T4 [PlainTV a_1627390695] [] [])
In the expression: $(reify 'T4 = fail . show)
In an equation for `dumpT4': dumpT4 = $(reify 'T4 = fail . show)
Dump.hs:14:12:
TyConI (NewtypeD [] M.N1 [] (NormalC M.W1 [(NotStrict,ConT
GHC.Types.Int)]) [])
In the expression: $(reify 'N1 = fail . show)
In an equation for `dumpN1': dumpN1 = $(reify 'N1 = fail . show)
Dump.hs:15:12:
TyConI (DataD [] M.N3 [PlainTV a_1627390694] [] [])
In the expression: $(reify 'N3 = fail . show)
In an equation for `dumpN3': dumpN3 = $(reify 'N3 = fail . show)
Dump.hs:16:12:
TyConI (NewtypeD [] M.N4 [PlainTV a_1627390693] (NormalC M.W4
[(NotStrict,ConT GHC.Types.Int)]) [])
In the expression: $(reify 'N4 = fail . show)
In an equation for `dumpN4': dumpN4 = $(reify 'N4 = fail . show)
Failed, modules loaded: M.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] no time profiling on my MacBookPro8,1
For this vanilla program module Main where main = print $ fib 40 fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) with these commands $ ghc -prof -auto-all -rtsopts -O --make Main.hs -o Main $ ./Main +RTS -p all of the %time cells in the generated Main.prof file are 0.0, as is the total time count (0.00 secs and 0 ticks). The %alloc cells seem normal. Andy Gill noticed that if you compile with -threaded, the %time cells seem normal. I scanned the GHC Trac tickets specific to Mac OS X, but saw no titles that looked similar. Is this a known issue? Thanks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] no time profiling on my MacBookPro8,1
Whoops: I'm running Haskell Platform 2011.2.0.1. OS X 10.6.7 i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664) (if that matters?) Out of my depth here. On Fri, May 6, 2011 at 5:07 PM, Nicolas Frisby nicolas.fri...@gmail.com wrote: For this vanilla program module Main where main = print $ fib 40 fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) with these commands $ ghc -prof -auto-all -rtsopts -O --make Main.hs -o Main $ ./Main +RTS -p all of the %time cells in the generated Main.prof file are 0.0, as is the total time count (0.00 secs and 0 ticks). The %alloc cells seem normal. Andy Gill noticed that if you compile with -threaded, the %time cells seem normal. I scanned the GHC Trac tickets specific to Mac OS X, but saw no titles that looked similar. Is this a known issue? Thanks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] what are the safety conditions for unsafeIOToST
I haven't been able to find it via Google or Haddock. An old message suggests is was just a matter of exceptions? I only want to use the IO for generating Data.Uniques to pair with STRefs in order to make a map of them. I'm guessing this would be a safe use since it's exception free (... right?). Thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] explicit big lambdas
Alternatively: let f :: some type involving a f = ... f' :: a - some type involving a f' _ = f in f' (undefined :: Int) normal f arguments On Thu, Mar 18, 2010 at 12:10 PM, Max Bolingbroke batterseapo...@hotmail.com wrote: Hi Paul, You should be able to introduce \Lambda at the source level by writing a type signature with an explicit forall. Similarly you can then instantiate these \Lambdas by using a type signature which is an instance of the foralled type at the use site: ~~~ -- id will get a \Lambda in Core id :: forall a. a - a id x = x -- this use of id will have Int applied as the first type argument in Core main = print $ (id :: Int - Int) 10 ~~~ This *should* extend smoothly to RankNTypes and other situations where GHC can't do good type inference. The typechecker doesn't know about big lambdas (they are added to Core by the desugarer from the output of the typechecker) so there is no better way to do this AFAIK. Cheers, Max On 18 March 2010 15:07, Paul Brauner paul.brau...@loria.fr wrote: Hi again, 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? If not: is there a way to provide ghc directly with core code before the type checking phase? Paul ___ 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 mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] idioms ... for using Control.Applicative.WrapMonad or Control.Arrow.Kleisli?
Each time I find myself needing to use the wrapping functions necessary for this embeddings, I grumble. Does anyone have a favorite use-pattern for ameliorating these quickly ubiquitous conversions? For runKleisli, I was considering something like okKleisli :: (Control.Arrow.Kleisli m a b - Control.Arrow.Kleisli m' a' b') - (a - m b) - (a' - m' b') onKleisli f = Control.Arrow.runKleisli . f . Control.Arrow.Kleisli but haven't really tested its usefulness. My most frequent use cases usually include Arrow.first, Arrow.second, , ***, or +++. E.g. somefun :: (Monad m, Num a) = (a, d) - m (a, d) somefun = onKleisli Control.Arrow.first (\ a - return (a + 1)) Perhaps a Control.Arrow.Kleisli, which would export (same-named) Kleisli specializations of all the Control.Arrow methods? And an analogous Control.Applicative.Monad? (Data.Traversable does this a little bit to specialize its interface for monads, such as Data.Traversable.sequence.) While writing this, I realized that you can't leave the Arrow-ness of Kleisli arrows implicit, since (-) a (m b) is two kinds of arrows depending on context -- which is precisely what the Kleisli newtype resolves. So I'm not seeing a reason to bring up the 'class Applicative m = Monad m where' dispute. Thanks for your time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] know a workaround for greedy context reduction?
I revisited the Strongly typed Heterogeneous Lists paper and read
about the import hierarchy technique. The basic idea is to delay
importing the instances until as late as possible, which prevents the
context simplification. The instances are effectively imported in the
top, Main module.
I'm thinking of exporting a MyLibrary.Main or MyLibrary.Instances module.
Anyone have experience with this approach in a library design? Is it
worth the user's extra import? Any pitfalls?
On Sun, Dec 7, 2008 at 4:57 PM, Nicolas Frisby nicolas.fri...@gmail.com wrote:
Seems I got ahead of myself with the bug search. I was thinking bug
because when I ascribe a type, I expect the compiler to check and then
respect it. With the most general type specification of the :type
command in mind, this does make sense. Thanks for improving my
internal notion of :type.
My grumble may seem more legitimate from a library perspective. I
implement a type-level function Append with three (preferably hidden)
ancillary classes and a single instance in order to support the
multiple modalities (in the Mercury sense) of the Append logic
function. When a user defines another function that uses the append
method, it's obfuscating for the user to see the internal classes in
the inferred type. That's what I would like to workaround.
If we consider class C the internal and consider class D and the
function f the library's exposed interface, then I'd like to see C
instead of D in the context of f and any function the user defines
with f, especially when I have supplied a preferred type for f.
f :: D a = () - a
f () = d
* :t f
f :: (C a) = () - a
No dice?
Thanks again,
Nick
On Sun, Dec 7, 2008 at 2:34 PM, Simon Peyton-Jones
simo...@microsoft.com wrote:
This is perfectly reasonable behavior I'm afraid. If you do :info d
you'll get d's original type signature. But :type takes an *arbitrary
expression* (in this case a single variable 'd', and figures out its most
general type. You could have said :t (3*3) for example.
In this case, when inferring the most general type of the expression d,
GHC tries to simplify the context (D a), and uses the instance declaration
to reduce it to (C a). And then it can't simplify it further. But you
*might* have had
instance C a
somewhere, in which case it'd have been able to simplify the (C a) away. So
GHC must try that route. If it fails, you want it to back up to a
notationally more convenient type, but GHC can't do that, I'm afraid
Simon
| -Original Message-
| From: haskell-cafe-boun...@haskell.org [mailto:haskell-cafe-
| boun...@haskell.org] On Behalf Of Nicolas Frisby
| Sent: 06 December 2008 03:23
| To: haskell Cafe
| Subject: [Haskell-cafe] know a workaround for greedy context reduction?
|
| With these three declarations
|
| {-# LANGUAGE FlexibleInstances #-}
| {-# LANGUAGE UndecidableInstances #-}
|
| class C a where c :: a
| class C a = D a where d :: a
| instance C a = D a where d = c
|
| ghci exhibits this behavior:
|
| * :t d
| d :: (C a) = a
|
| Where I would prefer d :: (D a) = a. In my actual examples, the
| context is much larger and I can't involve overlapping instances. Is
| there a known workaround? I didn't find a related bug on the GHC trac,
| and I don't know if other compilers behave in the same way.
| ___
| 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] Proposal for associated type synonyms in Template Haskell
Any movement on this? (I am actually just looking forward to generating kind ascriptions and having access to the kinds when processing TH.Dec, TH.Type, and such.) 2008/11/27 Simon Peyton-Jones simo...@microsoft.com: I've been away. I hope others will reply to this thread too; whatever you decide will end up in TH indefinitely. I know that Roman is interested in this. · You focus just on type families in class declarations (which is indeed where associated types started). But I suggest you also allow them at top level, as GHC does using the syntax type family T a :: * Indeed, since you propose to add to Dec, that'll happen automatically. But perhaps AssocTySynKindD is not a good name. Perhaps TySynFamilyD? · GHC uses type instance T [a] = Tree a as the way to add an equation to the definition of T. So perhaps TySynInstance rather than AssocTySynD? · I agree that it'd be good to do data type/newtype families at the same time. Roman needs this. · Your proposal for kinds looks fine. Simon From: haskell-cafe-boun...@haskell.org [mailto:haskell-cafe-boun...@haskell.org] On Behalf Of José Pedro Magalhães Sent: 11 November 2008 11:11 To: Haskell Cafe Subject: Re: [Haskell-cafe] Proposal for associated type synonyms in Template Haskell Hello Thomas, I see this is a proposal for a partial implementation of #1673 (http://hackage.haskell.org/trac/ghc/ticket/1673). Maybe it would be good if the remaining syntax (associated datatypes and type families) would also be defined and implemented in TH. Or maybe there isn't much demand for this?... Cheers, Pedro On Wed, Nov 5, 2008 at 15:57, Thomas van Noort tho...@cs.ru.nl wrote: Hello, Recently, we released a library on Hackage for generic rewriting (package rewriting if you are curious). The user of the library is expected to define type class instances to enable rewriting on his or her own datatypes. As these instances follow the datatype declarations closely, we tried to generate the instances using Template Haskell. Unfortunately, associated type synonyms are not yet supported by TH. After a presentation at the WGP'08, Simon encouraged us to write a proposal about adding associated type synonyms to TH, so that it can be added to GHC. So, here is our proposal. The TH AST must allow 1) kind declarations of associated type synonyms in class declarations and 2) their definitions in instance declarations. For example, class Foo a where type Bar a :: * instance Foo Int where type Bar Int = String The TH library defines a datatype Dec which contains a constructor for class declarations and instance declarations: data Dec = ... | ClassD Cxt Name [Name] [FunDep] [Dec] | InstanceD Cxt Type [Dec] ... 1) Associated type synonym kind declarations We suggest to add a constructor to the Dec type: ... | AssocTySynKindD Name [Name] (Maybe Kind) ... assocTySynKindD :: Name - [Name] - Maybe KindQ - DecQ The first field is the name of the associated type synonym, the second field is a list of type variables, and the third field is an optional kind. Since kinds are not yet defined in TH, we have to add some kind of kind definition (pun intended): data Kind = StarK | ArrowK Kind Kind type KindQ = Q Kind starK :: KindQ arrowK :: KindQ - KindQ - KindQ We explicitly choose not to reuse the Type type to define kinds (i.e., type Kind = Type as in GHC) since we think a separation between the two worlds is much clearer to the users of TH. 2) Associated type synonym definitions We suggest to add another constructor to the Dec type: ... | AssocTySynD Name [Type] Type ... assocTySynD :: Name - [TypeQ] - TypeQ - DecQ The first field is the name of the type synonym, the second field is a list of type arguments, and the third field is the body of the type synonym. We would like to hear your comments to this proposal. Regards, Thomas ___ 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 mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] know a workaround for greedy context reduction?
Seems I got ahead of myself with the bug search. I was thinking bug
because when I ascribe a type, I expect the compiler to check and then
respect it. With the most general type specification of the :type
command in mind, this does make sense. Thanks for improving my
internal notion of :type.
My grumble may seem more legitimate from a library perspective. I
implement a type-level function Append with three (preferably hidden)
ancillary classes and a single instance in order to support the
multiple modalities (in the Mercury sense) of the Append logic
function. When a user defines another function that uses the append
method, it's obfuscating for the user to see the internal classes in
the inferred type. That's what I would like to workaround.
If we consider class C the internal and consider class D and the
function f the library's exposed interface, then I'd like to see C
instead of D in the context of f and any function the user defines
with f, especially when I have supplied a preferred type for f.
f :: D a = () - a
f () = d
* :t f
f :: (C a) = () - a
No dice?
Thanks again,
Nick
On Sun, Dec 7, 2008 at 2:34 PM, Simon Peyton-Jones
[EMAIL PROTECTED] wrote:
This is perfectly reasonable behavior I'm afraid. If you do :info d you'll
get d's original type signature. But :type takes an *arbitrary expression*
(in this case a single variable 'd', and figures out its most general type.
You could have said :t (3*3) for example.
In this case, when inferring the most general type of the expression d, GHC
tries to simplify the context (D a), and uses the instance declaration to
reduce it to (C a). And then it can't simplify it further. But you *might*
have had
instance C a
somewhere, in which case it'd have been able to simplify the (C a) away. So
GHC must try that route. If it fails, you want it to back up to a
notationally more convenient type, but GHC can't do that, I'm afraid
Simon
| -Original Message-
| From: [EMAIL PROTECTED] [mailto:haskell-cafe-
| [EMAIL PROTECTED] On Behalf Of Nicolas Frisby
| Sent: 06 December 2008 03:23
| To: haskell Cafe
| Subject: [Haskell-cafe] know a workaround for greedy context reduction?
|
| With these three declarations
|
| {-# LANGUAGE FlexibleInstances #-}
| {-# LANGUAGE UndecidableInstances #-}
|
| class C a where c :: a
| class C a = D a where d :: a
| instance C a = D a where d = c
|
| ghci exhibits this behavior:
|
| * :t d
| d :: (C a) = a
|
| Where I would prefer d :: (D a) = a. In my actual examples, the
| context is much larger and I can't involve overlapping instances. Is
| there a known workaround? I didn't find a related bug on the GHC trac,
| and I don't know if other compilers behave in the same way.
| ___
| 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] know a workaround for greedy context reduction?
With these three declarations
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
class C a where c :: a
class C a = D a where d :: a
instance C a = D a where d = c
ghci exhibits this behavior:
* :t d
d :: (C a) = a
Where I would prefer d :: (D a) = a. In my actual examples, the
context is much larger and I can't involve overlapping instances. Is
there a known workaround? I didn't find a related bug on the GHC trac,
and I don't know if other compilers behave in the same way.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Could FDs help usurp an ATs syntactic restriction?
Perhaps this ticket is related?
http://hackage.haskell.org/trac/ghc/ticket/714
On Thu, Dec 4, 2008 at 9:38 PM, Nicolas Frisby [EMAIL PROTECTED] wrote:
From the error below, I'm inferring that the RHS of the associated
type definition can only contain type variables from the instance
head, not the instance context. I didn't explicitly see this
restriction when reading the GHC/Type_families entry.
Could perhaps the a b - bn functional dependency of the TypeEq
class lift this restriction for bn? This isn't my ball park, but that
idea has my hopes up :).
haskell
{-# LANGUAGE TypeFamilies #-}
import TypeEq
-- Attempting to encapsulate TypeEq behind an associated type.
class EQ a b where
type BN a b
instance TypeEq a b bn = EQ a b where
type BN a b = bn
/haskell
results in an error
ghci
/tmp/Test.hs:9:16: Not in scope: type variable `bn'
Failed, modules loaded: none.
/ghci
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] two type-level programming questions
1) Type families, associated types, synonyms... can anything replace the use of TypeCast for explicit instance selection? Section 2, bullet 4 of http://www.haskell.org/haskellwiki/GHC/AdvancedOverlap indicates a negative response. Any other ideas? 2) Any progress/options for kind polymorphism in instances? Thanks for your time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Could FDs help usurp an ATs syntactic restriction?
From the error below, I'm inferring that the RHS of the associated
type definition can only contain type variables from the instance
head, not the instance context. I didn't explicitly see this
restriction when reading the GHC/Type_families entry.
Could perhaps the a b - bn functional dependency of the TypeEq
class lift this restriction for bn? This isn't my ball park, but that
idea has my hopes up :).
haskell
{-# LANGUAGE TypeFamilies #-}
import TypeEq
-- Attempting to encapsulate TypeEq behind an associated type.
class EQ a b where
type BN a b
instance TypeEq a b bn = EQ a b where
type BN a b = bn
/haskell
results in an error
ghci
/tmp/Test.hs:9:16: Not in scope: type variable `bn'
Failed, modules loaded: none.
/ghci
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] template haskell overly conservative during splicing?
When using template haskell (via Derive) to generate this (exact) instance: instance Foldable ((-) Int) = Foldable Data.Derivable.InterpreterLib.Test.List where foldMap f (Cons x0 x1) = (const mempty Cons `mappend` foldMap f x0) `mappend` foldMap f x1 foldMap f (Nil) = const mempty Nil I realize the context is insatisfiable. My issue, is that I can't even reach that challenge. I get this error instead: Malformed type AppT ArrowT (ConT GHC.Base.Int) When splicing generated code into the program I couldn't find an existing ticket or discussion for this issue relying on the phrase malformed type. I couldn't even find the source that generates that string in haskell-src, template-haskell, or ghc-6.8.2. Can anybody help? Thanks for your time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] dangling symbolic links
I think I've exhausted my options without catching exceptions. If I have an invalid symbolic link, how can I identify that it exists? (Sorry about the line wrap.) tmp$ ls -l# no tricks up my sleeve, empty directory tmp$ touch foo tmp$ ln -s foo bar tmp$ ls -l total 8 lrwxr-xr-x 1 nfrisby nfrisby 3 Aug 27 23:29 bar - foo -rw-r--r-- 1 nfrisby nfrisby 0 Aug 27 23:29 foo tmp$ ghc -e 'System.Directory.doesFileExist bar' True tmp$ rm foo tmp$ ls -l total 8 lrwxr-xr-x 1 nfrisby nfrisby 3 Aug 27 23:29 bar - foo tmp$ ghc -e 'System.Directory.doesFileExist bar' # it follows the broken link False tmp$ ghc -e 'System.Posix.Files.fileExist bar'# the POSIX API also follows False tmp$ ghc -e 'System.Posix.Files.isSymbolicLink `fmap` System.Posix.Files.getFileStatus bar' # so does this one POSIX API also follows *** Exception: bar: getFileStatus: does not exist (No such file or directory) tmp$ ghc -e 'System.Posix.Files.isSymbolicLink `fmap` System.Posix.Files.getSymbolicLinkStatus bar' # the most successful so far True tmp$ rm bar # but it isn't an existence check... tmp$ ls -l tmp$ ghc -e 'System.Posix.Files.isSymbolicLink `fmap` System.Posix.Files.getSymbolicLinkStatus bar' *** Exception: bar: getSymbolicLinkStatus: does not exist (No such file or directory) Is there a way to check for the existence of a symbolic link without testing if getSymbolicLinkStatus raises an exception? This is with Darwin Kernel Version 8.11.1, GHC 6.8.2, directory-1.0.0.0, and unix-2.3.0.0. Thanks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: dangling symbolic links
Ah the magic of using a mailing list... I just realized that using getDirectoryContents lists the entry. Still, a doesLinkExist function might be nice... On Wed, Aug 27, 2008 at 11:46 PM, Nicolas Frisby [EMAIL PROTECTED] wrote: I think I've exhausted my options without catching exceptions. If I have an invalid symbolic link, how can I identify that it exists? (Sorry about the line wrap.) tmp$ ls -l# no tricks up my sleeve, empty directory tmp$ touch foo tmp$ ln -s foo bar tmp$ ls -l total 8 lrwxr-xr-x 1 nfrisby nfrisby 3 Aug 27 23:29 bar - foo -rw-r--r-- 1 nfrisby nfrisby 0 Aug 27 23:29 foo tmp$ ghc -e 'System.Directory.doesFileExist bar' True tmp$ rm foo tmp$ ls -l total 8 lrwxr-xr-x 1 nfrisby nfrisby 3 Aug 27 23:29 bar - foo tmp$ ghc -e 'System.Directory.doesFileExist bar' # it follows the broken link False tmp$ ghc -e 'System.Posix.Files.fileExist bar'# the POSIX API also follows False tmp$ ghc -e 'System.Posix.Files.isSymbolicLink `fmap` System.Posix.Files.getFileStatus bar' # so does this one POSIX API also follows *** Exception: bar: getFileStatus: does not exist (No such file or directory) tmp$ ghc -e 'System.Posix.Files.isSymbolicLink `fmap` System.Posix.Files.getSymbolicLinkStatus bar' # the most successful so far True tmp$ rm bar # but it isn't an existence check... tmp$ ls -l tmp$ ghc -e 'System.Posix.Files.isSymbolicLink `fmap` System.Posix.Files.getSymbolicLinkStatus bar' *** Exception: bar: getSymbolicLinkStatus: does not exist (No such file or directory) Is there a way to check for the existence of a symbolic link without testing if getSymbolicLinkStatus raises an exception? This is with Darwin Kernel Version 8.11.1, GHC 6.8.2, directory-1.0.0.0, and unix-2.3.0.0. Thanks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] cabal build command and package versions
I have a question about cabal's behavior for the build command. When using the build command on a cabalized project, any version changes for installed packages go unnoticed - the necessary modules in the project are not re-compiled. If however, you run the configure command (though the .cabal file for the project has not changed) and then the build command, the appropriate modules (and only the appropriate modules) are re-compiled. Not knowing that the configure command is necessary to detect changes in package that the current project depends on and proceeding only with the build command has led to BusErrors and GHC incurring the impossible in my exploration. Is there a reason that the build command does not check the packages for version changes? It seems fair to expect package-sensitivity of the process that determines if modules need to be re-compiled. This process, I think, is part of the build command and not the configure command. Here's an example scenario: - Imagine package Q depends on package P. - We runhaskell Setup.hs clean/configure/build/install them both, from scratch, at version 0. - Then we change package P (by, say, introducing new fields to a constructor that Q cases over), bump its version to 1, and runhaskell Setup.hs clean/configure/build/install on it. - If we now runhaskell build on package Q, nothing is re-compiled, though a package dependency has changed. runhaskell Setup.hs build does not notice this. - However, if we runhaskell configure/build on package Q, then the (necessary) modules are re-compiled. Thanks for your time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data Types a la Carte - automatic injections (help!)
I have accomplished this in two ways. Either drop the reflexive rule and introduce a void sentinel type or use TypeEq (... you said everything was fair game!) to explicitly specify the preference for the reflexive case over the inductive case. An advantage of TypeEq is that you can avoid overlapping (and also incoherent) instances and so play nice with functional dependencies. A disadvantage is its hyper-instability in terms of regressions via compiler development (none yet, though). There are better participants in the cafe for explaining the details if you choose this path. HTH On Mon, Jul 28, 2008 at 11:03 PM, Brandon S. Allbery KF8NH [EMAIL PROTECTED] wrote: On 2008 Jul 28, at 23:23, Kenn Knowles wrote: What confuses me is that IncoherentInstances is on, but it is still rejected by GHC 6.8.3 seemingly for being incoherent. I haven't tried it with any other version. Am I missing something? Any suggestions or pointers? Er? Looks to me like it wants the OverlappingInstances language extension. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MonadPlus
It sounds like the semantics of the MonadPlus methods are under-specified. I recall once writing a newtype wrapper to treat the same non-determinism monad with different mplus semantics, akin to cut versus backtracking. I think of MonadPlus as a less expressive version of msplit, from Backtracking, Interleaving, and Terminating Monad Transformers The Functional Pearl paper by Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry. ICFP 2005. Is that an over-simplification? On Fri, May 9, 2008 at 3:12 PM, Bryan O'Sullivan [EMAIL PROTECTED] wrote: Andrew Coppin wrote: ...so it's a kind of choice operator? Run all actions until you get to one that succeeds and return the result from that? In the context of Parsec, yes. In the grander scheme of things, the behaviour depends on whatever is appropriate for the particular monad you're working in. So, for example, mplus for lists is (++) and mzero is [], which is quite a different set of behaviours from the Parsec case. Usually, you can rely on MonadPlus behaving like a monoid. There are occasional exceptions, which is a mite upsetting. http://www.haskell.org/haskellwiki/MonadPlus b ___ 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] OT: Isorecursive types and type abstraction
This paper, with a pdf available at Patricia Johann's publications page http://crab.rutgers.edu/~pjohann/ seems to be related. Initial Algebra Semantics is Enough! Patricia Johann and Neil Ghani. Proceedings, Typed Lambda Calculus and Applications 2007 (TLCA'07) Hope that helps. On Jan 24, 2008 11:02 AM, Edsko de Vries [EMAIL PROTECTED] wrote: On Thu, Jan 24, 2008 at 10:46:36AM -0600, Antoine Latter wrote: Hmm ... How about: Perfect :: * - * = Fix (L :: * - *) . /\ A . (A + L (A,A)) unfold Perfect = [L := Fix L . t] t where t = /\ A . (A + L (A,A)) = /\ A . (A + (Fix L . /\ B . (B + L (B,B))) (A,A)) assuming alpha-equality. Because L and (Fix L . t) are of kind (* - *), the substitution should be okay. Am I missing something, again? The problem is not that Perfect as it stands cannot be unrolled; the problem is that without some hackery, I don't know how to unroll the type of a term if that type is of the form ((Fix ..) applied to some arguments rather than just (Fix ..) -- whether that is List or Perfect. The only reason I mention Perfect is that for List I can 'lift' the /\A over the Fix, but I cannot do that with Perfect. Edsko ___ 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] Haskell purity and printing
Extensionality says that the only observable properties of functions are the outputs they give for particular inputs. Accepting extensionality as a Good Thing implies that enabling the user to define a function that can differentiate between f x = x + x and g x = 2 * x is a Bad Thing. Note that your h does not differentiate between f and g (in fact, it does not investigate them at all), the only thing you can do with f, g, (h f), and (g f) is apply them. Accordingly, it's a fine Haskell definition. Why is extensionality a good thing? might be a more enlightening question. My answer would quickly be outshone by others', so I'll stop here. On Dec 18, 2007 3:00 PM, Cristian Baboi [EMAIL PROTECTED] wrote: This is what I understand so far ... Suppose we have these two values: a) \x-x + x b) \x-2 * x Because these to values are equal, all functions definable in Haskell must preserve this. This is why I am not allowed to define a function like h :: (a-b) - (a-b) h x = x The reasons are very complicated, but it goes something like this: - when one put \x-x+x trough the function h, the compiler might change it to \x - 2*x - when one put \x-2*x trough the function h, the compiler might change it to \x - x + x And we all know that \x - 2*x is not the same as \x-x+x and this is the reason one cannot define h in Haskell ___ 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] Haskell purity and printing
This is a fine warning you both point out, but I would suggest that it distracts from the OP's question. The previous, germane discussion holds if we assume that i) both f and g have type Integer - Integer, ii) the compiler writer is not out to get us, and iii) the GMP library, if used by that compiler, is correct. Oh and also that the representations of the Integers involved do not require more memory than the user's computer has to offer. Anything else seem relevant? I do apologize for my noise if the OP was indeed thinking of + and * as unlawful methods of the Num typeclass. A nice property of Haskell is to note that a little confusion of math and Haskell can be very helpful to clear up some existing confusion about Haskell. On Dec 18, 2007 3:31 PM, Bertram Felgenhauer [EMAIL PROTECTED] wrote: Cristian Baboi wrote: This is what I understand so far ... Suppose we have these two values: a) \x-x + x b) \x-2 * x Because these to values are equal, all functions definable in Haskell must preserve this. Oh but you can distinguish these functions. Consider a x = x+x b x = 2*x data T = A | B deriving (Show, Eq) instance Num T where _ + _ = A _ * _ = B f :: (T - T) - T f y = y undefined main = print (f a) print (f b) which prints A, then B. The key point here is that a and b have type (Num a = a - a) and while well behaved Num instances certainly can not distinguish a and b, artificial ones like above can. Enjoy, Bertram ___ 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] Re: [Haskell] Nested guards?
It seems there is previous background here that I am unaware of. I'll chime in anyway. What you describe as the wrong semantics seems to me to be the more appropriate. I am inferring that your expected behavior is explained such that the first server match ought to fail (and fall through to the second server match) because the pattern in the let fails. This seems odd to me. If the parse test expression yields a Just constructor, then hasn't the first server match succeeded and we ought now commit to the let expression? I apologize if this should be obvious to anyone familiar with the extension. On Dec 4, 2007 2:46 PM, Neil Mitchell [EMAIL PROTECTED] wrote: Hi server text | Just xs - parse text = let x | field1 `elem` xs = error ... do one thing ... | field2 `elem` xs = error ... do something else ... in x server _ = error ... invalid request ... This now has the wrong semantics - before if parse text returned Just [] the error invalid request branch was invoked, now its a pattern match failure. I haven't used pattern guards that much (but will once Haskell' standardises them, or they get implemented in Hugs!), but their syntax seems quite natural. This extension seems to make it harder to understand them, and gives some nasty , | parsing issues for a human at least - quite possibly for a compiler too. Perhaps if you gave a little grammar for extended pattern guards (compared to the original) it would be easier to see how naturally they fit in. Thanks Neil ___ 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] RFC: demanding lazy instances of Data.Binary
I've got a first draft with the newtype and just an instance for list.
If you'd prefer fewer questions, please let me know ;)
0) I've cabalised it (lazy-binary), but I don't have anywhere to host it.
Would it be appropriate to host on darcs.haskell.org or HackageDB (yet?).
Suggestions?
1) The fact that serialisation is fully strict for 32760 bytes but not for
32761 makes the direct application of strictCheck intractable. Do you have
any ideas how to circumvent that?
((unLazy . decode . encode . Lazy) `asTypeOf` id) (take 32760 (repeat ())
++ undefined)
= undefined
((unLazy . decode . encode . Lazy) `asTypeOf` id) (take 32761 (repeat ())
++ undefined)
= lots of ()s and then undefined
2) Also, any suggestions for other datatypes to provide default instances
for? Tree type structures immediately raise the question of which traversal
should be the default. I'm learning towards providing none since the goal of
constant space usage actually depends on the serialisation order matching
how the deserialised tree will be traversed.
3) I don't think it is applicable in anyway whatsoever to strict types like
Int, Data.Set, and Data.Sequence? Counter-arguments?
4) Perhaps the tight correspondence between serialisation and traversal
necessary for constant space usage does indeed mean that the instance for
the lazy list is the only appropriate one to provide. Perhaps the Chunks
data type and a function splitN :: Int - [a] - Chunks [a] would also be
helpful.
Thanks!
16, 2007 12:45 PM, Don Stewart [EMAIL PROTECTED] wrote:
dons:
nicolas.frisby:
I've noticed a few posts on the cafe, including my own experience,
where the spine-strictness of the Binary instance for lists caused
some confusion. I'd like to suggest an approach to preventing this
confusion in the future, or at least making it easier to resolve.
Having decided that it is indeed appropriate for some standard
instances to be strict by default [1], I think it would be beneficial
to standardize an approach for expressing that a lazy instance is
expected. I propose the following newtype be added to Data.Binary. A
demonstration immediately follows.
newtype Lazily a = Lazily { unLazily :: a }
-- example instance
instance Binary a = Binary (Lazily [a]) where
-- lazy get and put
Now
[1..] = (unLazily . decode . encode . Lazily) [1..]
instead of
_|_ = (decode . encode) [1..]
This email is a request for comments on this concept. I think it is a
minimal way of expressing the intent that the serialisation be lazy
[2]. Please share any concerns or suggestions. I'll submit a patch
once the discussion is complete... or if it becomes inactive ;)
I think this is a good compromise: allowing laziness for those who need
it, in a clean manner. How about we provie
Data.Binary.Lazy
with the Lazy newtype, and lazy instances for types that make sense to
be so?
For now, this can be developed as a single module depending on
Data.Binary . What do you think, Nick?
I'd like to also use strictCheck, as we did for the stream fusion
library, to state and check strictness properties for the instances,
since getting this clear and correct seems to be a common FAQ with
Binary.
-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RFC: demanding lazy instances of Data.Binary
In light of this discussion, I think the fully spine-strict list instance does more good than bad argument is starting to sound like a premature optimization. Consequently, using a newtype to treat the necessarily lazy instances as special cases is an inappropriate bandaid. My current opinion: If Data.Binary makes both a fully strict list instance (not []) and a fully lazy list instance (this would be the default for []) available, then that will also make available all of the other intermediate strictness. I'll elaborate that a bit. If the user defines a function appSpecificSplit :: MyDataType - [StrictList a], then the user can control the compactness and laziness of the serialisation by tuning that splitting function. Niel's 255 schema fits as one particular case, the split255 :: [a] - [StrictList a] function. I would hesitate to hard code a number of elements, since it certainly depends on the application and only exposing it as a parameter maximizes the reusability of the code. Related action: Thus I think that instead of a standard newtype to denote laziness expectations, there ought to be a standard strict list data type and Binary instance AND some documentation popularizing this as a possible optimization whenever the generated bytestrings from []s are too big. Is Data.Sequence suitable for use as StrictList? Or perhaps something from the strict library? I'm not fully savvy to the head-strictness/unpacking differences and trade-offs. Reaching for the sky idea: Does the Put monad offer enough information for an instance to be able to recognize when it has filled a lazy bytestring's first chunk? It could cater its strictness (i.e. vary how much of the spine is forced before any output is generated) in order to best line up with the chunks of lazy bytestring it is producing. This might be trying to fit too much into the interface. And it might even make Put an actual monad ;) On Nov 19, 2007 4:16 PM, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2007-11-19 at 13:39 -0800, Don Stewart wrote: nicolas.frisby: I've got a first draft with the newtype and just an instance for list. If you'd prefer fewer questions, please let me know ;) 0) I've cabalised it (lazy-binary), but I don't have anywhere to host it. Would it be appropriate to host on [1]darcs.haskell.org or HackageDB (yet?). Suggestions? You can host it on code.haskell.org, ask for an account here: I think we should consider if a lazier serialisation of lists shouldn't be the default first before thinking about forking the whole library. It depends on how much laziness you want. We could certainly make it so that this is true: (decode . encode) [1..] = [1..] rather than giving _|_. However the approach of Data.Binary is lazy serialisation but in chunks, big chunks. So while the above may be true, this would not be: (head . decode . encode) [1, _|_] = 1 because we generate 32k chunks of data when serialising. But do you really need it to be this lazy? Would it enough for it to be lazy in chunks. There is a good argument I think that the current fully strict serialisation is bad just from a performance perspective, and that instead we should serialise lists semi-lazily, using a chunked representation. For example Neil's serialisation library uses length prefixed chunks with a maximum chunk size of 255. The end of a list is denoted by a 0 length final chunk. This has the advantage that we only have to force a limited number of elements (to find the length) before serialising. If you want it really lazy then it would have to flush after each element to create a new lazy bytestring chunk. Note that flushing this often looses many of the performance advantages of the Data.Binary stuff. 1) The fact that serialisation is fully strict for 32760 bytes but not for 32761 makes the direct application of strictCheck intractable. Do you have any ideas how to circumvent that? Test using a much smaller chunk size. I'd test sizes from 1 to something like one more than the machine word size. 2) Also, any suggestions for other datatypes to provide default instances for? Tree type structures immediately raise the question of which traversal should be the default. I'm learning towards providing none since the goal of constant space usage actually depends on the serialisation order matching how the deserialised tree will be traversed. Lazy Arrays? 3) I don't think it is applicable in anyway whatsoever to strict types like Int, Data.Set, and Data.Sequence? Counter-arguments? Well, atomic types like Int, I don't think it makes sense, but Sets and Sequence are lazy, aren't they? Sequences are like spine strict lists. Sets are strict in as much as the element type's (==) function is strict. 4) Perhaps the tight correspondence between serialisation and traversal necessary for constant
Re: [Haskell-cafe] RFC: demanding lazy instances of Data.Binary
On Nov 19, 2007 4:16 PM, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2007-11-19 at 13:39 -0800, Don Stewart wrote: nicolas.frisby: *snip* 1) The fact that serialisation is fully strict for 32760 bytes but not for 32761 makes the direct application of strictCheck intractable. Do you have any ideas how to circumvent that? Test using a much smaller chunk size. I'd test sizes from 1 to something like one more than the machine word size. Let me clarify circumvent that. strictCheck uses a bounded search starting at 1 and proceeds to some limit. The Binary instance used in the example was the fully lazy one for lists: a get/putWord8 for each constructor. Even so, it was effectively spine-strict up to 32k bytes (which was 32k elements b/c of the use of unit) because (I think that) the first chunk of the lazy bytestring wasn't being generated by encode until it was full. If you asked strictCheck to go from 1 to 32k, I don't think it would finish. So by circumvent, I mean: How can we apply the essential ideas of strictCheck when our chunks are so big? Obviously, the iterative search cannot just proceed by one element at a time; but then we lose the obvious meaning of add one more _|_. I don't see an obvious candidate for how to alter the _|_-ridden test vector generation. Moreover, it's proposed output is wrong when considered from the Big Chunks perspective--we don't necessarily want Chitil's least strictness. (more new text below) 2) Also, any suggestions for other datatypes to provide default instances for? Tree type structures immediately raise the question of which traversal should be the default. I'm learning towards providing none since the goal of constant space usage actually depends on the serialisation order matching how the deserialised tree will be traversed. Lazy Arrays? 3) I don't think it is applicable in anyway whatsoever to strict types like Int, Data.Set, and Data.Sequence? Counter-arguments? Well, atomic types like Int, I don't think it makes sense, but Sets and Sequence are lazy, aren't they? Sequences are like spine strict lists. Sets are strict in as much as the element type's (==) function is strict. Let me refine how I posed that question. A predicate: if you enter Package.fromList [1..] at the ghci prompt and you get no intermediate results, then that was a strict type. I'm assuming that if the Show instance doesn't produce intermediate results, then the serialisation technique can't handle intermediate results (i.e. chunking) either--at least not in a general enough way to include it in a library. *snip* ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] cabal Main-Is restriction
It seems the meaning of the -main-is switch for GHC and the Main-Is build option for Cabal executables differ. With GHC, I can point to any function main in any module, but in Cabal I must point to a filename with precisely the module name Main. This is tying my hands with regard to organizing a default executable and exposing some of its functionality as a library. Is there a way to get around this restriction? Concretely, I want to point Cabal's Main-Is to Program/Main.hs which starts with module Program.Main where instead of just module Main where Is this currently possible? I recognize the add a separate Program-Main.hs file workaround, but I'll avoid it if I can. Thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RFC: demanding lazy instances of Data.Binary
I've noticed a few posts on the cafe, including my own experience,
where the spine-strictness of the Binary instance for lists caused
some confusion. I'd like to suggest an approach to preventing this
confusion in the future, or at least making it easier to resolve.
Having decided that it is indeed appropriate for some standard
instances to be strict by default [1], I think it would be beneficial
to standardize an approach for expressing that a lazy instance is
expected. I propose the following newtype be added to Data.Binary. A
demonstration immediately follows.
newtype Lazily a = Lazily { unLazily :: a }
-- example instance
instance Binary a = Binary (Lazily [a]) where
-- lazy get and put
Now
[1..] = (unLazily . decode . encode . Lazily) [1..]
instead of
_|_ = (decode . encode) [1..]
This email is a request for comments on this concept. I think it is a
minimal way of expressing the intent that the serialisation be lazy
[2]. Please share any concerns or suggestions. I'll submit a patch
once the discussion is complete... or if it becomes inactive ;)
Thanks for your time,
Nick
1 - One solution is to make all standard Binary instances lazy
wherever possible, but I presume that in most cases it's not needed
and the compactness gained through default strictness (such as the []
instance) is quite significant.
2 - A more involved option is to recognize that serialisation always
maps to a sequence, and so create another standard data type and
class.
data Chunks a = Empty | Chunk !a (Chunks a) -- a la lazy bytestrings
instance Binary a = Binary (Chunks a) where
-- lazy put and get
class Chunky a chunk | a - chunk where
toChunks :: a - Chunks chunk
fromChunks :: Chunks chunk - a
All of this machinery, however, may prematurely emphasize
problem-specific concerns. Thus it obfuscates the point: we just want
sufficient laziness. Whatever ends up happening, the Chunks data type
may be a route so common for Lazily instances that it makes sense to
provide it in a library (?
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/strict-0.2).
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do you trust Wikipedia?
It is truly irresponsible to post such interesting links on a mailing list! :) I resent and thank you for the last couple hours. On 10/17/07, Dan Weston [EMAIL PROTECTED] wrote: I find the mathematics is more accurate on http://www.conservapedia.com Their facts get checked by the Almighty Himself! ;) Dan Piponi wrote: The mathematics is probably the most reliable part of Wikipedia. -- Dan On 10/17/07, PR Stanley [EMAIL PROTECTED] wrote: Hi Do you trust mathematical materials on Wikipedia? Paul ___ 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 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] Primitive Recursive Algebraic Types
It seems you are confusing the notion of counting the number of operators in the expression with actually evaluating the expression. Your evalLength function does both. It may help to consider counting the number of operators in the expression to be the same as calculating the height of the syntax tree representing the expression. This is why when we are counting the operators in the expression, there is no need to distinguish Add and Sub; they are both just operators for this analysis and their different semantics are not yet a concern. The countOperators function need not distinguish between Add and Sub since we're not yet evaluating. Similarly, a literal is not an operator; the integer it contains is a value, not an operator. In this case the type Int is being used for two different reasons; you'll need to be able recognize it when this happens. Here's the correct version; you were quite close! In terms of types and recursive structure, you had it correct. By separating counting operators from evaluation, I think you'll clearly see the reasons for the definition. countOperators :: Expr - Int countOperators = heightOfTree heightOfTree (Lit n) = 0 heightOfTree (Add e1 e2) = 1 + (heightOfTree e1) + (heightOfTree e2) heightOfTree (Sub e1 e2) = 1 + (heightOfTree e1) + (heightOfTree e2) On 8/2/07, Alexteslin [EMAIL PROTECTED] wrote: Alexteslin wrote: Hi, I am doing some simple exercises about recursive algebraic types and this particular exercise asks to define a function which counts the number of operators in an expression. I defined the function below, but i am not sure if on the second line changing from evalLength (Lit n) = n to (Lit n) = 0 is the right solution. although the function produces correct result. data Expr = Lit Int | Add Expr Expr | Sub Expr Expr deriving (Eq, Show) evalLength :: Expr - Int evalLength (Lit n) = 0 evalLength (Add e1 e2) = 1 + (evalLength e1) + (evalLength e2) evalLength (Sub e1 e2) = 1 + (evalLength e1) - (evalLength e2) Thank you It actually doesn't work. Initially i tested on Add operator only. But whith Sub operator it produces wrong result. -- View this message in context: http://www.nabble.com/Primitive-Recursive-Algebraic-Types-tf4207521.html#a11969804 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ 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] Indentation woes
A bandaid suggestion: longFunctionName various and sundry arguments = f where f | guard1 = body1 f | guard2 = body2 | ... where declarations (Disclaimer: untested) As I understand it, there can be guards on the definition of f even if it takes no arguments. Those guards can reference your the various and sundry arguments. On 7/26/07, Stefan O'Rear [EMAIL PROTECTED] wrote: On Thu, Jul 26, 2007 at 02:56:57PM -0400, anon wrote: Greetings, I wish to be able to indent my code like so: longFunctionName various and sundry arguments | guard1 = body1 | guard2 = body2 | ... where declarations That is, with guards and where clauses indented to the same level as the function name. This seems like a perfectly reasonable indentation style to me. It also happens to be the preferred style in Clean, another layout-sensitive functional language. I believe it is not uncommon in ML dialects as well. So why is it that I'm not allowed to use it in Haskell? Because in Haskell everything that is lined up is a new logical line. Haskell requires all continuation lines to be indented: longFunctonName various and sundry arguments | guard1 = body1 | guard2 = body2 | .. where declarations As for why, it's just a matter of Haskell Committee taste. Nothing too deep, just an arbitrary set of rules. Stefan -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFGqPS5FBz7OZ2P+dIRAgwbAKCl3ssl6X42VqSZJnhgKVH7WSzRXwCaA3x5 Ze0lGvx17IDrFXxBEvVxGeI= =5/To -END PGP SIGNATURE- ___ 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] Re: advantages of using fix to define rcursive functions
Another advantage here - an analog I'm always eager to point out - is
that just as we can augment functions if they haven't yet been fixed,
we can augment functors. One can extend datatypes and functions (a la
open functions) or generically generate constructs such as (co-)free
(co-)monads in this way.
On 7/26/07, Dan Piponi [EMAIL PROTECTED] wrote:
On 7/26/07, Nicolas Frisby [EMAIL PROTECTED] wrote:
Trying to summarize in one phrase: you can do interesting
manipulations to functions before applying fix that you cannot do to
functions after applying fix (conventional functions fall in this
second category).
Something similar holds for types where we can use something like
data Fix s a = In{out :: s a (Fix s a)}
to construct fixed points of functors, as opposed to functions. Any
recursive type can be expressed using Fix, so the question is, why
would you do it? Well, associated to every recursive type is a
corresponding fold and unfold, of which the familiar foldr and unfoldr
are special cases for the List type. If we define our types using Fix
of some functor, then we can also have fold and unfold built for us
automatically from the functor, alongside the actual type.
There are a number of papers that discuss this, including The Essence
of the Iterator Pattern by Jeremy Gibbons and Bruno C. d. S.
Oliveira.
--
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] Indentation woes
Whoops, read too fast. Sorry for the noise. On 7/26/07, Stefan O'Rear [EMAIL PROTECTED] wrote: On Thu, Jul 26, 2007 at 02:58:21PM -0500, Nicolas Frisby wrote: A bandaid suggestion: longFunctionName various and sundry arguments = f where f | guard1 = body1 f | guard2 = body2 | ... where declarations (Disclaimer: untested) As I understand it, there can be guards on the definition of f even if it takes no arguments. Those guards can reference your the various and sundry arguments. Eh? Mine doesn't use up a where clause and doesn't use a f noise symbol. Why do you need a band-aid? longFunctionName\32=\n\32|\32guard\32=\32body\n\32|\32guard\32=\32body\n\32... Stefan -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFGqP3jFBz7OZ2P+dIRAgGhAKC3X7hV/vLElQelqCtjZ7XlZQDvdACfftJc R2g03ScWG33jSzGJ8yxJvUM= =rq9Y -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: advantages of using fix to define rcursive functions
Just casting my vote for the helpfulness of this reference. Trying to summarize in one phrase: you can do interesting manipulations to functions before applying fix that you cannot do to functions after applying fix (conventional functions fall in this second category). On 7/26/07, Chung-chieh Shan [EMAIL PROTECTED] wrote: You might enjoy this paper: Bruce J. McAdam, 1997. That about wraps it up: Using FIX to handle errors without exceptions, and other programming tricks. Tech. Rep. ECS-LFCS-97-375, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh. http://www.lfcs.informatics.ed.ac.uk/reports/97/ECS-LFCS-97-375/ -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig It is the first responsibility of every citizen to question authority. Benjamin Franklin ___ 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] Maintaining the community
Perhaps an information retrieval pipedream, but what if we attempted an automated FAQ answerer? I'm sure some keywords pop-up often enough in certain chunks of first posts (heterogenous lists, existential error messages, SOE and graphics, category functor monad, etc). It could respond with the standard links to the Wiki pages and research papers. Of course we would want to keep it on a leash for a while during training and taming. If we integrate it with the list, it might even belay the list message, giving the user a chance to read its response before selecting: * not quite helpful, send to list anyway * never send me this rubbish again Or we could avoid such invasive methods all together and just auto-post a rather comprehensive answer. Just a neat thought -- and another potentially nifty and well-sought tool written in Haskell. On 7/13/07, Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 13 Jul 2007, brad clawsie wrote: to improve the list, might i suggest - push chatter to IRC This is problematic for some kinds of techie chatter, where email makes it easier to get all the maths down. - take this service off of email entirely. try a web forum system (you may have to slum it and use php). i don't recommend nntp, that just forces us to use gmane since very few isps provide nntp now. a web forum would allow you to segment interest sections while retaining a global search etc. if you use code like slash, you can just moderate noise makers off the page. you can set up a yahoo group in ten minutes. A global search might be an idea to add to our existing archives, otherwise I'm still not convinced. -- [EMAIL PROTECTED] Society does not owe people jobs. Society owes it to itself to find people jobs. ___ 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] Maintaining the community
FYI, Gmail *can* kill threads, the Geniuses just deemed it unworthy of a UI presence. This is news to me and related to earlier comments in this thread. HTH http://mail.google.com/support/bin/answer.py?hl=enanswer=47787 On 7/13/07, Nicolas Frisby [EMAIL PROTECTED] wrote: Perhaps an information retrieval pipedream, but what if we attempted an automated FAQ answerer? I'm sure some keywords pop-up often enough in certain chunks of first posts (heterogenous lists, existential error messages, SOE and graphics, category functor monad, etc). It could respond with the standard links to the Wiki pages and research papers. Of course we would want to keep it on a leash for a while during training and taming. If we integrate it with the list, it might even belay the list message, giving the user a chance to read its response before selecting: * not quite helpful, send to list anyway * never send me this rubbish again Or we could avoid such invasive methods all together and just auto-post a rather comprehensive answer. Just a neat thought -- and another potentially nifty and well-sought tool written in Haskell. On 7/13/07, Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 13 Jul 2007, brad clawsie wrote: to improve the list, might i suggest - push chatter to IRC This is problematic for some kinds of techie chatter, where email makes it easier to get all the maths down. - take this service off of email entirely. try a web forum system (you may have to slum it and use php). i don't recommend nntp, that just forces us to use gmane since very few isps provide nntp now. a web forum would allow you to segment interest sections while retaining a global search etc. if you use code like slash, you can just moderate noise makers off the page. you can set up a yahoo group in ten minutes. A global search might be an idea to add to our existing archives, otherwise I'm still not convinced. -- [EMAIL PROTECTED] Society does not owe people jobs. Society owes it to itself to find people jobs. ___ 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] CPS versus Pattern Matching performance
This might be a feasible appropriation of the term destructor. On 7/10/07, Bruno Oliveira [EMAIL PROTECTED] wrote: On Tue, 10 Jul 2007 10:53:35 +0200 (MEST), Henning Thielemann wrote: On Tue, 10 Jul 2007, Tony Morris wrote: A foldr without recursion. I use such functions frequently in order to hide constructors of a data type. Does this kind of functions has a common name? I think they just called case analysis; at least that's the terminology used here: http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/concon.pdf (See the treeCase example in Section 3). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] advice: instantiating/duplicating modules
I wrote a combination reader/writer monad (a la the RWS monad in the mtl) and I find myself wanting to use multiple instances of it in the same stack of transformers. The functional dependencies prevent this from working out. The class is called MonadRW and the transformer is called RWT. I find myself wishing I could import the same module twice, but instead of having two names for the same entity, I want the definitions proper of the module to be duplicated: I want two separate MonadRW classes and two separate RWT transformers. Since the module integrates the MonadRW and RWT transformer with the mtl, I would then only need to lift the instances of the instantiated MonadRW classes through the other RWTs. I'm rather unfamiliar with Template Haskell, but it sounds like it might fit the bill. Although, if I recall correctly, instances and type declarations splicing are yet to be implemented in GHC? Does anyone have any advice how to do this? I'm envisioning some preprocessing. I'd like to know if someone has developed a tool for this already or if this path has been attempted. Thanks for your time, Nick PS - If this doesn't work out, I'm aware that I could use type-indexed products and coproducts to pull it off, but I think that would drastically reduce the number of people who could understand/maintain the code without having to learn such cool stuff. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Collections
Just a couple of examples: many non-trivial program analyses (like optimizations or type-inference) rely on viewing the AST as a graph. Graph reduction is an evaluation paradigm, and I'm guessing that a (specification-oriented) interpreter might use a graph. On 6/20/07, Andrew Coppin [EMAIL PROTECTED] wrote: David House wrote: Andrew Coppin writes: Data.Graph -- graph type What would you use that for? (And what does it do?) It's for graphs, in the graph-theory [1] sense. Yes, I realise that. (I'm not a graph theory expert, but I'm aware of the subject.) But what kind of thing would you use a general graph for? (Rather than some more specific custom data type.) Data.Tree -- rose tree type What's a rose tree? (I only know about binary trees. Well, and N-ary trees... but nobody uses those.) Well, it is said that a rose tree by any other name would be just as N-ary. (I think they're the same concept :)). LOL! I asked Wikipedia about rose tree and got something quite different... ;-) ___ 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] Collections
I don't know where you got the notion that such structures are not available in Haskell. There are many efficient data structures in the libraries. Lists are not magical, just popular, natural, and traditional. Specialized data structures are always important. Take a look at the Data.* modules in http://haskell.org/ghc/docs/latest/html/libraries/ Also see http://www.haskell.org/ghc/docs/edison/ There are many references to be found. You may want to cozy up with this one if you're really interested. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://books.google.com/books?id=SxPzSTcTalAC On 6/19/07, Andrew Coppin [EMAIL PROTECTED] wrote: When I was at university, we learned a programming language known as Smalltalk. I was rather good at it. [Ironically, making small talk is one of the things I do worst IRL! But anyway, back to the topic...] In Smalltalk, there is a wide selection of collection types, all with different facilities and efficiency trade offs. There is bag, set, list, array, ordered list, dictionary, hash table, weak array, etc. A whole menagerie of collection types. However, Haskell only has 1 type of collection: linked lists. (And only single-linked at that.) While other normal programming languages spend huge amounts of effort trying to select exactly the right collection type for the task in hand, Haskell programs only ever use linked lists. Why is that, exactly? Does writing software in Haskell magically change the properties of these data structures such that lists become more efficient than all the other types? Or is it that other data structures are only efficient when used with in-place updates? (The latter statement appears to be isomorphic to stating that Haskell programs must necessarily be less efficient than impure ones.) Thoughts? ___ 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] Mysterious monads
On 5/27/07, Andrew Coppin [EMAIL PROTECTED] wrote:
[snip]
such that a Reader is created with an initial list, and the read
function fetches 1 element out of that list. That is, the expression x
- read will take the head element of the list and put it into x,
keeping the tail to be read later.
Your intended behavior for Reader indicates stateful computational
features. The read later roughly expands to be read by some monadic
action on the rhs of a = as in
(read = \x - read {-this is later-} = ...)
Recognizing the stateful nature gives you two options:
1) Implement yours as a restricted version of Control.Monad.State
type ReaderAC = State
readAC = get = \x - put (tail x) return (head x)
2) or (as Isaac demonstrated) look to the definition of
Control.Monad.State.State for guidance own how to structure your
monad.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Currying: The Rationale
Disclaimer: I've not read the standard. Sections are de-sugared depending on which argument you supply: (x^) == (^) x (^x) == flip (^) x I think this is why they are considered special cases. Prelude map (^2) [1..10] [1,4,9,16,25,36,49,64,81,100] Prelude map (flip (^) 2) [1..10] [1,4,9,16,25,36,49,64,81,100] Prelude map (2^) [1..10] [2,4,8,16,32,64,128,256,512,1024] Prelude map ((^) 2) [1..10] [2,4,8,16,32,64,128,256,512,1024] On 5/23/07, Chad Scherrer [EMAIL PROTECTED] wrote: On 5/23/07, Philippa Cowderoy [EMAIL PROTECTED] wrote: On Wed, 23 May 2007, Chad Scherrer wrote: Is (^2) really considered currying? As I understand it, this is syntactic sugar for a section, and might confuse the issue a bit, since it's distinct from ((^) 2). Sure, but it's (flip (^)) 2. Well, ok, but you've changed the definition. If it were enough for it to be equivalent to a curried version, we could as well write sq x = times (x,x) where times (x,y) = x * y and argue that this is partial application of a curried function because it's equivalent to the curried version you gave. But I guess I'm being a bit pedantic here, and I suspect your definition is exactly how (^2) is desugared. Chad -- [EMAIL PROTECTED] Sometimes you gotta fight fire with fire. Most of the time you just get burnt worse though. ___ 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] ambiguous type variables at MPTC
This is a question about some interesting behaviors in GHC's
typechecker regarding MPTCs. The brief code is at the bottom of the
message. By the way, the types can be inferred but not declared
without the forall and ascription in the where clause.
f1 below is illegal because we don't know what type the result of read
should be: it's type is ambigious.
Why isn't f2 illegal as well? If C had a functional dependency of a -
b, then I could understand accepting the type. However, without the
functional dependency, b might not necessarily be determined from a.
i) The above reasoning encroaches on the magic of TypeCast, which
effectively allows local functional dependencies to be declared at the
instance-level. Because of this, the typeclass mechanism might
effectively have a means of determining b from a without the class
being explicitly decorated with the functional dependency.
ii) Type errors where b really isn't determined by a are caught by
the typechecker wherever f2's arguments are instantiated (at some
usage site). This is convenient at times (it admits the uncertainty of
the might not necessarily) and annoying at others (debugging):
perhaps there's a ghc switch to disallow this?
If f2 is legal, why if f3 illegal? For some usage site of f3, the
constraint C String b might allow b to be resolved given whatever
instances of C are in effect.
Is there a motivation for these behaviors?
Are these sorts of cases discussed in the CHR/FD paper that motivated
the coverage condition (which I have yet to read)?
If ATs or GADTs would handle these situations differently, why so?
Should FDs also handle these situations differently?
Thanks for your time.
class C a b where
method :: a - b
{- illegal due to ambiguous variable
f1 :: forall a . (Read a) = String - ()
f1 x = ()
where _ = read x :: a
-}
-- legal, despite the lack of an FD (a - b) on C
f2 :: forall a b . (C a b) = a - ()
f2 x = ()
where _ = method x :: b
{- illegal due to none of the forall'd variables being reachable
from the type proper
f3 :: forall b . (C String b) = String - ()
f3 x = ()
where _ = method x :: b
-}
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Obscure instances for Obscure types
I've had a similar question, which I think boiled down to a compilation issue. Consider packages A and B that can be defined independently. But, just as Neil pointed out, perhaps A and B could also interact beyond their basic definition. My naive idea is that A would compile the simple independent way if B wasn't around and vice versa. But if A and B were both present at compile time, then their interaction would also be compiled. The open question is then where does that interaction live? I would guess this problem has been solved in other systems. Anything come to mind? On 4/26/07, Neil Mitchell [EMAIL PROTECTED] wrote: Hi I currently maintain two libraries, TagSoup which defines the Tag data type, and BinaryDefer, which defines the BinaryDefer class. If I wanted to include an instance for BinaryDefer Tag, where would I put it? Putting it in either library introduces an artificial dependency on the other. Putting it in a separate libary makes the library about 4 lines long and is just annoying. Putting it in the individual application(s) is exactly what libraries were designed to avoid. Is there a solution? Thanks Neil ___ 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] Tutorial on Haskell
Here here. This reminds me of a recent discussion on the cafe. Thee OP amounted to: What are the monad laws good for?. The answer was: It means the monad doesn't do surprising things and its behavior is congruent with the basic intuitions of sequenced computation. In my eyes, proving nice properties about programs and moreover calculating the programs themselves are pillars of computer science. However, I think it's helpful (for this sort of presentation crafting) to be aware of the disparity between computer science and most programming in the trenches. That said, Sylvan points out that the disparity isn't a unbridgeable schism--it's just that the concepts don't yet map as directly as we'd like. On 4/18/07, Sebastian Sylvan [EMAIL PROTECTED] wrote: On 4/18/07, Taillefer, Troy (EXP) [EMAIL PROTECTED] wrote: I have to strongly disagree with the statement that developers like to debug. Debugging is necessary because you can't reason about any sizeable piece of code just is not tractable even in Haskell. Now automated tools for reasoning about programs are very cool but lets face it no real world developer will sit down start to manually formally reason about large pieces of code. I think the emphasis when mentioning reasoning really shouldn't be you can reason formally about your programs and prove that they don't go wrong, nor when it has gone wrong, you can reason about the program to figure out why, it should be since the language doesn't do batshit insane things behind your back, your programs will mostly work the first time. The reasoning isn't an active task that you schedule time for, at least for a casual user like me, it's part of the actual programming. You do reasoning when writing in C++ as well, but you often get it wrong (because the language is, shall we say, unreasonable?) and that causes bugs. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ 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] Tutorial on Haskell
One technique I find compelling is (ab)using the type class system for meta programming. Something from Lightweight Static Resources, Faking It, or Hinze's Full Circle slides might be really attractive. Perhaps Danvy's Haskell printf? The hook might be: Yeah, you've heard of strong static typing and polymorphism, but did you know you could do this? Also: generic programming is always a hot topic. On 4/16/07, Simon Peyton-Jones [EMAIL PROTECTED] wrote: Friends I have agreed to give a 3-hr tutorial on Haskell at the Open Source Convention 2007 http://conferences.oreillynet.com/os2007/ I'm quite excited about this: it is a great opportunity to expose Haskell to a bunch of smart folk, many of whom won't know much about Haskell. My guess is that they'll be Linux/Perl/Ruby types, and they'll be practitioners rather than pointy-headed academics. One possibility is to do a tutorial along the lines of here's how to reverse a list, here's what a type is etc; you know the kind of thing. But instead, I'd prefer to show them programs that they might consider *useful* rather than cute, and introduce the language along the way, as it were. So this message is to ask you for your advice. Many of you are exactly the kind of folk that come to OSCON --- except that you know Haskell. So help me out: Suggest concrete examples of programs that are * small * useful * demonstrate Haskell's power * preferably something that might be a bit tricky in another language For example, a possible unifying theme would be this: http://haskell.org/haskellwiki/Simple_unix_tools Another might be Don's cpu-scaling example http://cgi.cse.unsw.edu.au/~dons/blog/2007/03/10 But there must be lots of others. For example, there are lots in the blog entries that Don collects for the Haskell Weekly Newsletter. But I'd like to use you as a filter: tell me your favourites, the examples you find compelling. (It doesn't have to be *your* program... a URL to a great blog entry is just fine.) Of course I'll give credit to the author. Remember, the goal is _not_ explain monads. It's Haskell is a great way to Get The Job Done. Thanks! Simon ___ 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] k-minima in Haskell
[sorry for the double, ajb] Since there seemed to be a disconnect between the expectation and the previous answers, I thought an alternative suggestion might help out. This sort of thing (haha) usually isn't my cup o' tea, so please point out any blunders. RM, is this more like what you had in mind? It leans more towards an iterative approach. If so, I encourage you to compare this to the other solutions and try understand how those solutions rely upon laziness. Stefan and Andrew, feel free to point out the drawbacks to this approach that I'm probably overlooking. kminima n l = map fst (foldr insert' (List.sort pre) suf) where (pre, suf) = (splitAt n . zip [0..]) l -- I think this insertion sort could be -- O(log k) with a better data structure. insert' x [] = [] insert' x (y : ys) | snd x snd y = x : y : dropLast ys' | otherwise = y : insert' x ys where dropLast ys = take (length ys - 1) ys We grab the first k elements and sort them, this list is our first approximation to the k-minima. We then process the rest of the list, checking if the current element is smaller than any of the minima of the current approximation. If the current element is smaller, we improve the current approximation by inserting the new element and dropping the biggest (i.e. last) minimum from the minima accumulator. The worst behavior is: sort(k) + (n-k) * k comparisons. This could be improved (to: sort(k) + (n-k) * log k comparisons, I think) with a better data structure for the minima approximation. On 4/12/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: G'day all. Quoting raghu vardhan [EMAIL PROTECTED]: So, any algorithm that sorts is no good (think of n as huge, and k small). The essence of all the answers that you've received is that it doesn't matter if k is small, sorting is still the most elegant answer in Haskell. The reason is that in Haskell, a function which sort function will produce the sorted list lazily. If you don't demand the while list, you don't perform the whole sort. Some algorithms are better than others for minimising the amount of work if not all of the list is demanded, but ideally, producing the first k elements will take O(n log k + k) time. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: k-minima in Haskell
Both Yitzchak's and my suggestions should run in constant space--some strictness annotation or switching to foldl' might be necessary. On 4/12/07, Mark T.B. Carroll [EMAIL PROTECTED] wrote: Dan Weston [EMAIL PROTECTED] writes: Ah, but which k elements? You won't know until you've drained your entire stream! True, but you still don't need to keep the whole stream in memory at once, just the k-least-so-far as you work your way through the stream - once you've read a part of the stream you can mostly forget it again. The question as I understood it was one of if even in Haskell there's a better way than sorting that means you need only have a fragment of the stream in memory at once. -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A convenient way to deal with conditional function composition?
Using the Endo newtype can avoid such ambiguities:
http://darcs.haskell.org/packages/base/Data/Monoid.hs
newtype Endo a = Endo { appEndo :: a - a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f `mappend` Endo g = Endo (f . g)
Endo allows you to explicitly select the monoid behavior of the
endomorphism String - String instead of using String - String as an
exponent. It seems 6.4.2 - 6.6 made a change from a default Monoid
instance for (a - a) to the more general Monoid instance for (a -
b).
On 4/10/07, Stefan O'Rear [EMAIL PROTECTED] wrote:
On Tue, Apr 10, 2007 at 02:33:41PM +0100, Chris Kuklewicz wrote:
Well, since ((.) :: ShowS - ShowS - ShowS) is a Monoid, you can use Writer
to
create the result:
Not portably.
[EMAIL PROTECTED]:~$ ghc-6.4.2 -e '( (foo++) `Data.Monoid.mappend` (bar++) )
END'
foobarEND
[EMAIL PROTECTED]:~$ ghc-6.6 -e '( (foo++) `Data.Monoid.mappend` (bar++) )
END'
fooENDbarEND
-- 6.6 sources
instance Monoid b = Monoid (a - b) where
mempty _ = mempty
mappend f g x = f x `mappend` g x
Stefan
___
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] Keeping a symbol table with Parsec
Section 2.12 of the Parsec manual[1] discusses user state. It sounds
like that is what you are after.
Hope that helps,
Nick
[1] - http://www.cs.uu.nl/~daan/download/parsec/parsec.pdf
On 4/2/07, Joel Reymont [EMAIL PROTECTED] wrote:
Folks,
Are there any examples of keeping a symbol table with Parsec?
I'm translating a parser from OCaml and I do this
OUTPUT COLON ID LP NUMERIC_SIMPLE RP
{ add $3 TypNumOut; SimpleOutputDec ($3, Number) }
Meaning that if a keyword Output is followed by : and an identifier
and then (NumericSimple) then add identifier to the symbol table as
a Number and box it in a constructor.
Then in my lexer I do a lookup to check if I have seen this
identifier and if I have seen one of type TypeNumOut I return the
token NUM instead of ID. This ensures that I can have rules with the
token NUM as opposed to ID everywhere.
How would I accomplish the same with Parsec, that is 1) update a
symbol table and 2) check identifiers and return a different token?
Thanks, Joel
--
http://wagerlabs.com/
___
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] A wish for relaxed layout syntax
I don't think that aName = [ x , y , z ] can be beat for adaptability (i.e. adding/removing/reorganizing results or _especially_ renaming the declaration). Doesn't do so hot regarding vertical space though... On 3/28/07, Greg Buchholz [EMAIL PROTECTED] wrote: David House wrote: I see this a lot. My personal preference is: mylist = [ foo, bar, baz, qux, quux, foo, bar, baz, qux ] Or, mylist = [foo, bar , baz, qux, quux, foo, bar, baz , qux] ___ 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] Re: A question about functional dependencies and existential
A wee bit off topic... but bear with me. Oleg points out a distinction between declaring a class with functional dependencies and implementing a class with functional dependencies. Judging from my experience, it might behoove those wrestling with type classes and FDs to emphasize that the class declaration also merely declares the functional dependencies and does not guarantee them as type-level functions. Moreover, instances implementing the class implement the functional dependencies as well. However, just because GHC accepts the instances as satisfying the functional dependencies, it doesn't necessarily guarantee that the functional dependencies can be aggressively used to resolve polymorphism--let me elaborate on this last point. Consider class C a b | a - b where foo :: a - b instance C Int Int where foo = id instance Num a = C Bool a where foo _ = 3 GHC 6.7.20070214 accepts this code with fglasgow-exts and undecidable instances. I usually read the functional dependencies as a determines b (and I suspect many other people do as well). Unfortunately, that is not the guaranteed by the functional dependency analyzer. What is guaranteed is that any two instances of C do not together contradict the functional dependencies. Given C Bool x, I cannot infer what x is, though I had thought that a determines b. When I was exercising my prefrontal Olegial cortex in writing my own static record library a la Hlist, I learned this lesson the hard way. Hopefully this saves the reader some trouble. Motto: appeasing the functional dependency analyzer DOES NOT mean that the type class is actually a type function. Perhaps ATs do have this quality? I'm not sure--but if they do I will definitely be a fan. On 3/28/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: class T root pos sel | pos - root, root - sel where f :: pos - sel - Bool instance T root (Any root) sel But the same applies to the second functional dependency and the type variable sel. Every instantiation of root determines the instantiation of sel. And that forbids instance T Int (Any Int) Bool and instance T Int (Any Int) Int inside the same scope, doesn't it? Indeed that is your intent, expressed in the functional dependency. It may help to think of a class declaration as an `interface' and of the set of instances as an `implementation' (of the type class). In the example above, the class T root pos sel _declares_ a ternary relation T and specifies some `constraints'. The set of instances of T (in our example, there is only one instance) specifies the triples whose set defines the relation T. In Herbrand interpretation, an unground instance instance C1 x y = C (Foo x) (Bar y) corresponds to a set of instances where the free type variables are substituted by all possible ground types provided the instance constraints (such as C1 x y) hold. In our example, an unground instance |instance T root (Any root) sel| is equivalent to a set of ground instances where |root| and |sel| are replaced with all possible ground types. Including instance T Int (Any Int) Bool instance T Int (Any Int) Int These two instances are in the model for `instance T root (Any root) sel'. A set of instances, an implementation of a type class, must satisfy the interface, that is, constraints imposed by the class declaration, including the functional dependency constraints. In our example, any implementation of T must satisfy root - sel constraints. The above two instances show there exists a model of T where the functional dependency is violated. That's why both GHC 6.4 and Hugs reject the instance. Again, it is a mystery why GHC 6.6 accepts it. ___ 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] Re: Why the Prelude must die
Gut feeling: the quick'n dirty script case occurs far less than the whole module case. Thus I think the benefit of automatically importing the Prelude if the module declaration is omitted should not happen: the Principle of Least Surprise out-weighs the small benefit to a rare case. Correct me if I'm wrong about my hunch that the quick'n dirty case is rare. Even so, I have a healthy respect both for Least Surprise and a minimal number of behaviors when it comes to compilers. My vote would be to never automatically import the Prelude, at least not by default. Regarding type variable naming, a few of my more hardware minded friends I've asked to try Haskell often tease me about the opaque type variable names in the Prelude--it seems greater consideration of type variable names in the Prelude might behoove new users. On 3/27/07, Lennart Augustsson [EMAIL PROTECTED] wrote: I agree, I think this is what we need. Plus a decision of what names the builtin syntax refers to, like the type of 'a'. -- Lennart On Mar 26, 2007, at 23:30 , Ashley Yakeley wrote: Sebastian Sylvan wrote: The solution is simple: * If there is a module M where clause in the beginning of the file, then it's a proper module and shouldn't import the Prelude. * If there is no module declaration then it's a quick'n dirty script and should have the Prelude implicitly imported. * Interactive interpreters should probably import the Prelude. That should take of most issues. I think this is ideal. I've always thought writing import Prelude was a good idea if one wants one's module to import the Prelude. It's one less corner case. -- Ashley Yakeley ___ Libraries mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/libraries ___ 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] ghc warning Var/Type length mismatch
When I load my program, GHC spits these messages at me, but doesn't
fail Any idea what might be causing this or how to figure that out?
Var/Type length mismatch:
[]
[a{tv aGIf} [tau]]
...
Var/Type length mismatch:
[]
[a{tv aGN8} [tv]]
...
I found the responsible code in GHC's darcs, but the context didn't
lend any help my feeble non-GHC hacker brain.
My program is kind of big and I'm using personal libraries that
exercise the type system a lot, but I'll wait to see if anyone is
interested or if this has been handled before I share the gory
details. This tidbit might help: I have a couple of usages of
undefined in my program b/c I'm just starting to code and if I replace
a particular undefined of this with some typed dummy code, it removes
the second set of mismatches, but not the first. I tried also
replacing the other undefined, but the first set of mismatches
remained.
Glasgow Haskell Compiler, Version 6.7.20070214, for Haskell 98,
compiled by GHC version 6.7.20070214
Also, is there a better list for this question? I half-heartedly tried
haskell.org's list of mailing lists for an appropriate place for GHC
bugs but didn't find one.
Thanks for your time,
Nick
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] There can be only one fix? Pondering Bekic's lemma
Whooops. Thanks for the correction. On 3/20/07, Levent Erkok [EMAIL PROTECTED] wrote: On 3/19/07, Nicolas Frisby [EMAIL PROTECTED] wrote: Nope, but I believe the two are equipotent. This usage of believe is one of those I think I remember reading it somewhere usages. On 3/19/07, Henning Thielemann [EMAIL PROTECTED] wrote: On Sat, 17 Mar 2007, Nicolas Frisby wrote: Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x - fix (\y - f (x, y))) = fix f where f :: (a, a) - a The 'fix' on the right hand side is not the standard one (e.g. Control.Monad.Fix), is it? Yes, it is the standard fix. The Bekic lemma actually reads: fix (\x - fix (\y - f (x, y))) = fix (\x - f (x, x)) which should explain the confusion here. -Levent. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fix
In effect, this is a demonstration that Haskell supports recursive values and not just recursive functions. If the a in fix :: (a - a) - a were to be unified always with a function type, then that would imply that the language only supported recursive definitions for functions, which would be a bit unfortunate for the co-coders in the community. It's good to note that simple languages with a strict evaluation scheme are limited to fix :: ((a - b) - (a - b)) - (a - b) because functions are the only things that can delay evaluation. On 3/20/07, Paul Hudak [EMAIL PROTECTED] wrote: Assuming 1 :: Int, then: ones = 1 : ones is equivalent to: ones = fix (\ones - 1:ones) where fix has type ([Int] - [Int]) - [Int]. It's also the case that: inf = 1+inf is equivalent to: inf = fix (\inf - 1+inf) where fix has type (Int - Int) - Int. Unfortunately (perhaps), the fixed point returned is _|_, since it is the LEAST solution to the recursive equation. -Paul Dan Weston wrote: But in fact it seems to me that the type variable a not only can, but must unify with b-c. Is there any use of fix for which this is not true? If this is true, is the type a instead of b-c because it is not possible in general for the type checker to verify this fact, making it some kind of underivable true statement? If it is not true, I would dearly love to see a use of fix with a type for which functional application is not defined. For me, it is this aspect (the type of fix) that has made it so much harder to understand fix than it should have been. 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] There can be only one fix? Pondering Bekic's lemma
Nope, but I believe the two are equipotent. This usage of believe is one of those I think I remember reading it somewhere usages. On 3/19/07, Henning Thielemann [EMAIL PROTECTED] wrote: On Sat, 17 Mar 2007, Nicolas Frisby wrote: Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x - fix (\y - f (x, y))) = fix f where f :: (a, a) - a The 'fix' on the right hand side is not the standard one (e.g. Control.Monad.Fix), is it? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] There can be only one fix? Pondering Bekic's lemma
Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x - fix (\y - f (x, y))) = fix f where f :: (a, a) - a This depends on having true products, though I'm not exactly sure what that means. Mutual recursion can also be described with recursion and products f = \a - ... g a ... g = \b - ... f b ... can be defined as (f, g) = fix (\knot - \a - ... (snd knot) a ..., \b - ... (fst knot) b ...) My question is: Given products and a fixed point combinator, can any pure expression be transformed into a corresponding expression that has just a single use of fix? If yes, has there been any usage of such a transformation, or is it just crazy? If no, could you provide a counter-example? Thanks for playing along, Nick [1] - Bekic has an entire book, but the most available reference for this I found is Levent Erkök's thesis regarding MonadFix/mfix (pgs 16 and 141). [Also, I cannot figure out how to get the proper symbol above that c in Bekic... sorry about that. I'd appreciate if someone told me how; does Unicode even have it?] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] N and R are categories, no?
That said, N and R are indeed categories; however, considering them as categories should be carefully interlaced with your intuitions about them as types. I haven't formally checked it, but I would bet that this endofunctor over N, called Sign, is a monad: Sign x = x + x Pos = injectLeft Neg = injectRight unit = Pos join (Pos (Pos n)) = Pos n join (Pos (Neg n)) = Neg n join (Neg (Pos n)) = Neg n join (Neg (Neg n)) = Pos n Pos and Neg are just labels for sign. I'm assuming N is the naturals, not the integers; thus this monad might actually be useful :). Also note that this means there is not necessarily a mapping from F x - x. Neg 3 should not necessarily map to 3. Also, this structure is probably satisfies many more laws than just the monad laws--e.g. monoids or monoidals. So while it might not always make sense to consider N and R as categories when learning about category theory and Haskell, it might be helpful to learn about monads (and other notions) in categories simpler than the Fun category of functional types and partial functions--N and R are could be good categories for such learning. Have fun! On 3/15/07, Ulf Norell [EMAIL PROTECTED] wrote: On 3/15/07, Steve Downey [EMAIL PROTECTED] wrote: EOk, i'm trying to write down, not another monad tutorial, because I don't know that much yet, but an explication of my current understanding of monads. But before I write down something that is just flat worng, I thought I'd get a cross check. (and I can't get to #haskell) Monads are Functors. Functors are projections from one category to another such that structure is preserved. One example I have in mind is the embedding of the natural numbers into the real numbers. The mapping is so good, that we don't flinch at saying 1 == 1.0. Monads are endofunctors (functors from one category to itself). This is easy to see from the type of join: join : m (m a) - m a For Haskell monads the category is the category of Haskell types and Haskell functions. In this category N and R are objects, so you'll get the wrong idea trying to see them as categories. / Ulf ___ 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] N and R are categories, no?
Thanks for keeping me honest ;) On 3/15/07, Dominic Steinitz [EMAIL PROTECTED] wrote: I haven't formally checked it, but I would bet that this endofunctor over N, called Sign, is a monad: Just to be picky a functor isn't a monad. A monad is a triple consisting of a functor and 2 natural transformations which make certain diagrams commute. If you are looking for examples, I always think that a partially ordered set is a good because the objects don't have any elements. A functor is then an order preserving map between 2 ordered sets and monad is then a closure (http://en.wikipedia.org/wiki/Closure_operator) - I didn't know this latter fact until I just looked it up. Dominic. ___ 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] Re: Maybe and partial functions
It seems like we could refine the first parameter of carryPropagate just as the second: make an= type N1 that only admits values [1..]. Would not that suffice to prove that base is never 0 and not have to go beyond the type-checker for a proof? On 3/13/07, Neil Mitchell [EMAIL PROTECTED] wrote: Hi Note: Total = total ignoring non-termination, for this post Surely we can assume them total given that base is never zero? They are not total, they are called in a manner which does not cause them to raise an error. If you want every function to be total, you need to fix div. If you are happy with individual functions being partial, provided the program as a whole is total, that's fine (and I'd agree with you!). However, in this case you need to either prove that the program won't crash, or stop calling it total. This corresponds to proving that base is never zero. Of course, if you're going to just accept a proof that base is never zero, why not just accept a proof that head/tail are called on an infinite list? It says you defining codata, and your own versions of head/tail/drop etc I have a machine checkable (and machine generated) proof that base is never zero, and the list is infinite. Thanks Neil ___ 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] Usage of . and $
Which is the longer way of saying you don't need to count to make sure you closed all the brackets you opened! ;-) Dougal Stanton 1) Emacs does the counting for me 2) parens don't surprise me if I happen to use rank-2 types. i was bit enough times when learning why $ and runST don't like each other that I've grown averse of $. I also like thinking of building a composite function instead of sequencing applications--this has helped me see patterns in other places like writing monad transformer instances and other stuff, so maybe it's a good thing. My 2 cents. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Usage of . and $
I don't use rank-2 types that often and when I do I'm aware of the restriction on ($) and similar hofs. I tend to use ($) only when the right-hand side gets very messy; a multiple-line do or similar. For example: blah = fromMaybe $ do x - blah1 y - blah2 guard (x == f y) g x The closing parenthesis would make things a little messy, so ($) is nice. -David House, [EMAIL PROTECTED] For this situation, I go ahead and name the subcomputation with a where clause or a do-let binding. Usually, naming sub terms can't hurt. Other than look at Darcs or GHC, has there been any efforts for (very general, libertarian even) coding guidelines? Suggestions tips might be a better word. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Usage of . and $
sum . IntMap.elems . IntMap.IntersectionWith (\x y - x*y) queryVector rationalProjection Composition with (.) builds a function, but you eventually want an Int, so we can't just use (.), but we can come pretty close. (sum . IntMap.elems . IntMap.IntersectionWith (\x y - x*y) queryVector) rationalProjection ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Takusen and strictness
The deep, dark, Aslan magic of getContents is usually safe to use because it's a read-only operation. Some of the dangerous corners of getContents are: what happens if the file is altered while we read it lazily? This is the sort of question that the sequencing notion of the IO monad is supposed to solve by saying: we read it all at once, so no one can alter it while we do that. (getContents might lock the file--I don't know, but that would introduce its own corner cases). Can a database fetch have such magic? I think yes, it could probably be implemented the exact same way as getContents. However, whereas concurrent access to files on a filesystem is rare and hence a corner case, concurrent access to a database is usually the norm, and hence not a corner case. In that sense, runSqlLazily might be a helpful function that is often dangerous for A-Consistency-ID reasons. However, ACID-like concerns are not new for DB people, so if the DB server supports transactions, then perhaps Takusen could set up a server-maintained transaction and then read it on-demand. At this point, my arms have become weary from all of the hand-waiving, so I'll ask for discussion now... On 3/2/07, Paul Moore [EMAIL PROTECTED] wrote: On 02/03/07, Bayley, Alistair [EMAIL PROTECTED] wrote: There's a big difference between getContents and Takusen: getContents has a non-trivial implementation (using unsafeInterleaveIO) that allows it to return data lazily. Takusen has no such implementation. ... ie, there's deep dark magic involved in the seemingly simple getContents, which isn't easily available to mere mortals (or even semi-immortal library designers). That figures. It's a shame, but not totally unsurprising. That's what my earlier code looked like, and I found it harder to understand than the getContents/process/put approach. I'm trying to explore ways of factoring data manipulation code out of database access functions, but maybe that's not the right way of doing it. I don't think it's possible to pursue this style of programming with Takusen. If you do, you'll have to process the entire result-set into a data structure and then process it, which has obvious memory implications. Oh, well. It's mostly irrelevant for me anyway, as the data sets I'm actually playing with are small enough that slurping them into memory isn't an issue - so I just choose between a simple and decoupled implementation or a more complex and scalable one, which is a fairly standard optimisation choice. Thanks for clarifying. Paul. ___ 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] Automatic Recognition of Functors
This link might be what you are after: http://okmij.org/ftp/Haskell/typecast.html#deepest-functor On 3/1/07, Walter Potter [EMAIL PROTECTED] wrote: Folks, Given f:: a - b it is very natural to lift f to P f :: P a - P b where P is the power set functor. Or L f :: [a] - [b]. We are modeling structures using repeated application of the power functor, via repeated application of [ ]. It would be very nice if Haskell would recognize this lifting. That is, if f :: a - b then one automatically has f :: [a] - [b] without using fMap. We can do something similar with classes in the following way: Given class Addy a where (+.) :: a - a - a instance(Addy a) = Addy [ a] (+.) w [ ] = w (+.) [ ] w = w (+.) (a:as) (b:bs) = (a+b) :(as + bs) Now given instance Addy Int (+.) x y = x+y One can compute [[1,2],[3,4]] +. [ [2,3],[1,2,.3]]. I know I'm asking for a bit more here. I might need to use fMap f : [ a] - [ b]. But I can't seem to get by with fMap f [[1,2],[3,4]] when f :: Int - Int We often need to lift functions to higher power maps. It would be nice to have a way to do this with ease. Suggestions are welcome. Walt ___ 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] What inhabits this type: (forall a. a - b) - (forall a. m a - m b)
The type doesn't actually indicate that the type m supports a return operation. I introduced the qualifier that it was a functor. You implicity introduced the constraint that it is a monad (actually a pointed functor, but that's a Monad's return operator). With that constraint, your thought process seems fine to me. On 2/27/07, Bryan Burgers [EMAIL PROTECTED] wrote: Since my last query was answered so quickly, let's try another. I have looked on Hoogle. I would have asked Djinn, but I don't have it around. So, can someone find a term that inhabits (forall a. a - b) - (forall a. m a - m b) ? I think of this as the type of functions that, given a function from any boxed-up a to a b, will give me a function from a boxed-up ma to a m b -- m does not have to be a Monad!. Jacques (Jacques, sorry you got this twice--I forgot to send it to the list.) How about this one? f g x = return $ g x Since 'g' can, by definition, take any type and return a 'b', then it should be able to take some 'm a' and return something of type 'b', which we just return. I'm not really familiar with foralls, but the two explicit foralls make the two a's different, right? (After reading the other responses, I must be wrong, but can somebody explain why?) Bryan Burgers ___ 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] exists . a psuedo-standard non-empty list module
Despite the fact that I like head/fromJust etc, a safe list library would be kind of handy. If someone wants to roll that into the Safe library, as Safe.List or something, I'd be happy to accept patches (saving someone else the hassle of setting up a new library etc, for roughly the same purpose) Thanks Neil That sounds like a great option. Candidate numero uno as of now. What I have in mind right now should be pretty light weight, but it will mostly be a regurgitation of code I've seen floating around. Some of the code from the previous wiki link, type-level decimal numbers I saw in an Oleg paper (I think), etc. Would you be open to such code in your library? Anyone have a better place for it? Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie question about denotational semantics
I'm still getting my head around this myself, but I know a few references that might help (maybe not directly, but they're in the ballpark). 1 I believe the phrase natural lifting or naturality of liftings is what you're after when you attempt to compare a monad and a bigger monad that includes the affects of the first. I recall this concept from Liang and Hudak's modular monadic semantics work, but I'm having a heck of a time quickly finding it in their papers. Try at least section 8.1 in Monad Transformers and Modular Interpreters. 2 Another example that helped me when getting a feel for reasoning about monadic code (which is the basis of what we're doing here) was William Harrison's Proof Abstraction for Imperative Languages ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie question about denotational semantics
[my mail program hiccuped and chopped my message, sorry] 2 Another example that helped me when getting a feel for reasoning about monadic code (which is the basis of what we're doing here) was William Harrison's Proof Abstraction for Imperative Languages. It uses monads and some of the notions like the ones you're in search of. 3 Lastly, we're reasoning about folds with denotational semantics. Graham Hutton's Fold and Unfold for Program Semantics was a great read for me. Using its techniques will likely shorten up any proof we've got. This is some of my favorite stuff, let me know how you fare with it! Good luck, Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Map list of functions over a single argument
Here comes an overwhelming post (so stop here if you're not interested
in applicative functors), but apfelmus stepped in this direction. The
funny part is that, modulo dictionary passing (which might be compiled
away), all 6 functions below do the Exact Same Thing because of
newtype erasure (Calling all experts: am I right about that?).
All of the themes below are explained in the Applicative Functors
pearl, which is an excellent read. See:
http://lambda-the-ultimate.org/node/1137
The aha! this code attempts to illuminate is that the point that
'maps' can be written as the sequencing of the environment monad is
akin to saying that all regular polygons have a perimeter as opposed
to all 2-dimensional shapes have a perimeter. Both are obviously
legitimate claims, but we might be able to squeeze a little more
understanding out of the second version. A more germaine formulation:
it's not the monadic properties of the environment reader that we need
in order to solve this problem so much as it is the applicative
functor properties of the environment reader (which also happens to be
a monad).
Moreover, it doesn't just work for lists of functions--e.g. it could
work for trees too. The required property here is captured by
Data.Traversable, which the list type constructor satisfies. Use of
traversable often comes hand-in-hand with applicative functors.
\begin{code}
import qualified Control.Monad as M
import Control.Monad.Reader
import qualified Control.Applicative as AF
import qualified Data.Traversable as T
-- Nothing Fancy Here:
-- to avoid confusion with monad during this presentation,
-- we create a newtype for environment as an applicative functor
newtype ReaderAF r a = ReaderAF { runReaderAF :: r - a }
instance Functor (ReaderAF r) where
fmap fn (ReaderAF f) = ReaderAF (fn . f)
instance AF.Applicative (ReaderAF r) where
pure a = ReaderAF (const a)
(ReaderAF f) * (ReaderAF g) = ReaderAF (\r - (f r) (g r))
-- our target functions
maps, mi_maps, me_maps, afe_maps, afi_maps, maf_maps :: [a - b] - a - [b]
-- conventional
maps fs a = map ($ a) fs
-- monadic (implicit reader)
mi_maps fs a = (M.sequence fs) a
-- monadic (explicit reader)
me_maps fs a = runReader (M.sequence fs') a
where fs' = map Reader fs
-- applicative functor (explicit reader)
afe_maps fs a = runReaderAF (T.sequenceA fs') a
where fs' = map ReaderAF fs
-- applicative functor (implicit reader)
afi_maps fs a = (T.sequenceA fs) a
-- combination (a monad as an applicative functor)
maf_maps fs a = runReader (AF.unwrapMonad (T.sequenceA fs')) a
where fs' = map (AF.WrapMonad . Reader) fs
\end{code}
Also, Data.Traversable exports a function 'sequence' that generalizes
the one from Control.Monad/Prelude to work on more than just lists:
Prelude :m + Data.Traversable
Prelude Data.Traversable :t Data.Traversable.sequence
Data.Traversable.sequence :: (Traversable t, Monad m) = t (m a) - m (t a)
So we could have even written 4 more versions of the function that
again all reduce to the same thing (modulo dictionary passing)!
It isn't really highlighted above, but one high-level difference
between monads and applicative functors is a question of how paramount
is the notion of sequencing (the = kind of sequencing more so than
the 'sequence' kind of sequencing).
Sorry for the dropping the concept bomb on a simple question, but
hopefully someone enjoyed the adventure.
Nick
On 2/20/07, David House [EMAIL PROTECTED] wrote:
On 20/02/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
It's also known as
sequence :: Monad m = [m b] - m [b]
with m = (-) a
Don't forget to import Control.Monad.Instances for this to work.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]
You took my quote entirely out of context. In particular, you omitted the rest of the sentence but I'm sure that day will come. My statement was no excuse by any stretch of the imagination--I was initially confused when I saw it in your post and then a bit offended. The original intent of my statement was as a preface to the fact that I enjoyed reading the discussion and appreciated everyone's involvement. On that note, thanks for participating. I recognize the particular excuse you intended my quote to represent, but I think it was inappropriate to chop my quote to suit your needs--it makes me seem short-sighted in the eyes of the community when, ironically enough, it was actually part of a prediction that I will need performance from my Haskell someday. I do feel a little defamed, but I don't want to go off topic on the list, especially for personal issues. Just try to consider the affect it will have on others when looking for quotes in the future. Thanks and no worries, Nick On 2/19/07, Melissa O'Neill [EMAIL PROTECTED] wrote: Sorry, I'm a little late to this thread, but the topic of sieve [] = [] sieve (x:xs) = x : sieve [y | y - xs, y `mod` x /= 0] (as posted by Rafael Almeida) is somewhat dear to my heart, as I wrote a paper about it last summer and sent it in to JFP. Still waiting for a reply though. Let's go back to the beginning with the classic complaint and the excuses... Creighton Hogg wrote: So a friend and I were thinking about making code faster in Haskell, and I was wondering if there was a way to improve the following method of generating the list of all prime numbers. It takes about 13 seconds to run, meanwhile my friend's C version took 0.1. Here come the excuses, like this one from apfelmus, While Haskell makes it possible to express very complicated algorithms in simple and elegant ways, you have to expect to pay a constant factor (roughly 2x-10x) when competing against the same algorithm in low-level C. and this one from Nicolas Frisby, I have yet to need my Haskell to perform well Matthew Brecknell came up with something much faster, namely primes :: [Int] primes = 2 : filter isPrime [3,5..] where f x p r = x p*p || mod x p /= 0 r isPrime x = foldr (f x) True primes FWIW, another way to write this code (without needing to think about how fold bails early) is primes = 2: [x | x −[3,5..], all (\p − x `mod` p 0) (factorsToTry x)] where factorsToTry x = takeWhile (\p − p*p = x) primes Both of these algorithms best the sieve we began with and run quickly, but as you can see (possibly more clearly from my rephrasing), this algorithm is not actually the Sieve of Eratosthenes -- it's actually a classic naive primes algorithm which checks a number for primality by trying to divide it by every prime up to its square root. But that's okay, because our initial algorithm ISN'T THE REAL SIEVE EITHER. Markus Fischmann hits the nail on the head when he says The characteristics of a sieve is, that it uses the already found primes to generate a list of non-primes that is then removed from a list of candiates for primeness. But then we get distracted by a discussion about avoiding division. It's true that the real sieve avoids division, but it is NOT true that every algorithm that avoids division is the sieve. The thread ends with this algorithm from Yitzchak Gale: -- Delete the elements of the first list from the second list, -- where both lists are assumed sorted and without repetition. deleteOrd :: Ord a = [a] - [a] - [a] deleteOrd xs@(x:xs') ys@(y:ys') | x y = y : deleteOrd xs ys' | x y = deleteOrd xs' ys | otherwise = deleteOrd xs' ys' deleteOrd _ ys = ys sieve (x:xs) = x : sieve (deleteOrd [x+x,x+x+x..] xs) sieve _ = [] primes = sieve [2..] Which seems reasonable, until you realize that every prime p we come up with is still considered by k deleteOrd filters, where k is the number of primes that preceeded it. So, let's recap: the original algorithm is beautiful and simple, but it is NOT the actual Sieve of Eratosthenes, NOT because it uses modulus, but because fundamentally, at the highest level, it is a different algorithm. At the risk of beating a dead horse, let's see why it's not the real sieve. What makes the sieve an efficient algorithm are the details of *what* gets crossed off, *when*, and *how many times*. Suppose that we are finding the first 100 primes (i.e., 2 through 541), and have just discovered that 17 is prime. We will begin crossing off at 289 (i.e., 17 * 17) and cross off the multiples 289, 306, 323, ... , 510, 527, making fifteen crossings off in total. Notice that we cross off 306 (17 * 18), even though it is a multiple of both 2 and 3 and has thus already been crossed off twice. (The starting point of 17 * 17 is a pleasing, but actually *minor*, optimization for the *genuine* sieve.) The algorithm is efficient because each composite number, c, gets crossed off f
[Haskell-cafe] our worst unsafePerformIO nightmares are upon us!
http://www.thinkgeek.com/geektoys/cubegoodies/86b8/ Now you can really show your coders why unsafePerformIO is to be avoided! -Nick ps - Please don't consider this post a product advertisement or endorsement of any kind. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] exists . a psuedo-standard non-empty list module
I don't particularly like using fromJust or head, and there's been plenty of discussion on those issues. For the cases where it makes good sense to do so, I'm about to write a module for non-empty lists that looks to strike a balance between usability and static checks. But before I re-invent the wheel, I was wondering if there's already a popular module along those lines. I would also appreciate references to your favorite discussion about uses of head and other unsafe functions or various Oleg posts showing how they're all unnecessary. I'll find these on my own, but I would also like to know which ones strike a chord with the community. Thanks for your time. -Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] SoC: Port Haddock to use GHC
One of my questions surely should have been: 5) Does haddock.ghc build? Does it work? I succeeded in getting it compiled (I filled in the missing data definition of DocOptions, hacked it to always use [] for the options anyway, manually set the compilerPath, and maybe more). Unfortunately it dies upon start-up: the GHC sub-session is panicing by accessing the static options global variable too early. This is over my head concerning GHC and Cabal internals. I'm really eager to use this, so I can help if need be. Thanks. On 2/15/07, David Waern [EMAIL PROTECTED] wrote: 15 feb 2007 kl. 18.19 skrev Nicolas Frisby: I am very ready for a Haddock that can swallow infix typenames. Yes, Haddock-GHC can do that. In dons's recent overview of the last SoC, a darcs repo for Waern's project was listed. I jumped at the link but couldn't find much documentation (i.e. the README file is GHC's, not the SoC project's). Some Google queries followed with no success. That repo is the GHC branch that I was working on, and it's not relevant anymore, since it has been merged into GHC HEAD. The repository for the actual program is at: http://darcs.haskell.org/SoC/ haddock.ghc My questions for Waern or anyone else who knows where to look: 1) Where to look for more complete documentation? There is no special documentation for Haddock-GHC yet. 2) Is the implementation integrated into GHC yet? GHC head? Separate repo? Yes, it is integrated in GHC HEAD. 3) What Haddock features are supported as of yet? Most of the things that was supported in Haddock in August, except for e.g. Hoogle output and such things. 4) Is it still actively developed. Yep, although not so fast :) /David ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
Guess this is a tricky choice for a foldr intro, since it requires a paramorphism (see bananas lenses wires etc.) para :: (a - [a] - b - b) - b - [a] - b para f e [] = e para f e (x:xs) = f x xs (para f e xs) -- note that the original tail of the list (i.e. xs and not xs') is used in the else-branch dropWhile' p = para (\x xs xs' - if p x then xs' else (x:xs)) [] Prelude dropWhile' (5) [1,2,3,4,5,6,7,8] [5,6,7,8] Prelude dropWhile' (5) [1,2,3,4,5,6,7,1] [5,6,7,1] Prelude :m + Test.QuickCheck Prelude Test.QuickCheck :m + Text.Show.Functions Prelude Test.QuickCheck Text.Show.Functions quickCheck $ \p l - dropWhile p (l :: [Int]) == dropWhile' p l Loading package QuickCheck-1.0 ... linking ... done. OK, passed 100 tests. On 2/12/07, Donald Bruce Stewart [EMAIL PROTECTED] wrote: pixel: Chris Moline [EMAIL PROTECTED] writes: dropWhile p = foldr (\x l' - if p x then l' else x:l') [] invalid: dropWhile ( 5) [1, 10, 1] should return [10, 1] Prelude Test.QuickCheck Text.Show.Functions quickCheck $ \p xs - dropWhile p xs == foldr (\x l' - if p x then l' else x:l') [] (xs :: [Int]) Falsifiable, after 4 tests: function [-1,-3,1] If in doubt, do a quick check! -- Don ___ 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] Foldr tutorial, Inspired by Getting a Fix from a Fold
Oops; I totally forgot the context of this whole discussion! I enjoyed your article. On 2/12/07, Bernie Pope [EMAIL PROTECTED] wrote: Nicolas Frisby wrote: Guess this is a tricky choice for a foldr intro, since it requires a paramorphism (see bananas lenses wires etc.) para :: (a - [a] - b - b) - b - [a] - b para f e [] = e para f e (x:xs) = f x xs (para f e xs) -- note that the original tail of the list (i.e. xs and not xs') is used in the else-branch dropWhile' p = para (\x xs xs' - if p x then xs' else (x:xs)) [] Actually, several people tried to use para, but of course it is not in the spirit of the challenge :) Cheers, Bernie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell soltion ofr I/O: is it monads or uniqueness types, after all?
Very rarely is a nontrivial solution the only way. Monads are a construct that nicely represents the sequencing side-effecting computations in a pure and strongly-typed environment. They are a nice way to do it, but certainly not the only one. Now I'm not confident enough to boldly make this claim, but perhaps they're the simplest way: i.e. they capture the essence of sequencing. Thoughts? On 2/10/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello haskell-cafe, just another interesting discussion in russian forum raised such idea: we all say that monads are the haskell way to do i/o. is it true? may be, uniqueness types, just like in Clean and Mercury, are real way, and monads are only the way to write programs that use uniqueness types easier? so, IO monad is like any other monad - it simplifies writing of complex code, but by itself it don't solve any problems. all code that can be written with monads can also be written using ordinal function calls. we know it for IO monad too - in ghc, we can use low-level representation of IO type and write imperative code without use of any monad operators -- Best regards, Bulat mailto:[EMAIL PROTECTED] ___ 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] Re: Optimization fun
A wee bit off topic, but I'm sure it's an acceptable detour. I just wanted to say that I appreciate both this sort of post and the consistent responses it solicits. I have yet to need my Haskell to perform well, but I'm sure that day will come. I like to follow these questions and hopefully be better prepared for those harsher times :). So thanks for the questions and the answers. On 2/10/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: You're right, 'fix' is *not* a fix for non-termination, this is better fixed in the type system (with the right fixed points or you're in a fix) ;) Fixed regards, apfelmus Lennart Augustsson wrote: This is actually a pretty good algorithm. And also a rather subtle one when it comes to termination. :) Of course, the best optimization is a better algorithm. In case this is what you're after, have a look at Colin Runciman, Lazy Wheel Sieves and Spirals of Primes http://citeseer.ist.psu.edu/runciman97lazy.html ___ 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] mtl tweaks
There have been some discussions of augmentations of the monad transformer library. I at least know there was a discussion regarding strictness of state/value components in the state monad transformer (I must admit I didn't track the conclusion of that one). I have another small mtl complaint: ReaderT, for example, requires the base type to be a Monad in order to make it a Functor. So it's Monad m = Functor (ReaderT r m) instead of Functor f = Functor (ReaderT r f), which is what's actually necessary for the instance. Remember, I did say _small_ complaint. I realize this has a bit to do with the class heirarchy and that's a sensitive issue. Regarding backwards compatibility and interface changes, note that the Monad m = Monad (ReaderT r m) instance would be unaffected by this... it's only the Functor = Functor instance. If someone wants to treat a transformed monad as a functor, then they're probably savvy enough to specify the base monad as a functor (especially with the @fmap f = (= return . f)@ recipe). They won't even see a difference unless they are rolling their own monad, since all mtl monads are also functors. 1) Is there a collection of these suggestions specifically for mtl? On the wiki? On the bug tracker? 2) Any chance we could make this change to the library? Thanks, Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State separation/combination pattern question
Another option is to use the HList library (though this can involve a
learning curve). Essentially your monad is a state monad and its state
is a big tuple constrained to contain at least whichever types you ask
of it. Consider
foo :: (HOccurs StateA st, ...other HList properties..., MonadState st m) = m
()
foo = do st - gets hOccurs -- note the gets hOccurs
put $ st { a = 1:(a st) }
bar :: (HOccurs StateB st, ...other HList properties..., MonadState st m) = m
()
bar = do st - gets hOccurs
put $ st { b = 2:(b st) }
When you use foo and bar together, the constraints the state of your
monad must satisfy accumulate, i.e. exec would require both HOccurs
properties of its monad's state.
This approach would stretch the type checker more than the others. And
I can't say I've ever used it on a large scale, but it has worked on
smaller examples. Also, too much polymorphism can cause some issues
with all of the library's type machinery.
But I think it's an attractive option if it fits your needs.
Good luck,
Nick
On 12/23/06, J. Garrett Morris [EMAIL PROTECTED] wrote:
On 12/22/06, Reto Kramer [EMAIL PROTECTED] wrote:
What I'm really looking for is not so much the chaining of StateT
compositions, but rather the isolation of StateA from StateB while
they both flow from the search loop into the respective library calls
(foo, bar) transparently to the application programmer. I'm hoping
there's a way to have the loop be in a State monad whose content is
the sum of the two states that are needed for the foo and bar call
made to the stores from inside the loop. The calls sites for foo and
bar should then extract the right component of the global state and
thread only that state through into the modules. Sounds like magic,
but how close can I get?
My first impulse would be to define classes for each type of state and
have a top-level monad which is instances of each of those. Using
your example: (your code is quoted, mine quoted)
-- ghci -fglasgow-exts ...
--
type StateA = [Integer]
At this point, I would add:
class Monad m = MonadStateA m
where getA:: m StateA
modifyA :: (StateA - StateA) - m ()
putA :: MonadStateA m = StateA - m ()
putA = modifyA . const
type StateB = [Integer]
And, similarly here:
class Monad m = MonadStateB m
where getB:: m StateB
modifyB :: (StateB - StateB) - m ()
putB :: MonadStateB m = StateB - m ()
putB = modifyB . const
data AppStateRec = AppStateRec { a :: StateA, b :: StateB } deriving
Show
These functions change in two ways: first, their type signatures now
use the new classes I defiend above. Second, by including the modify
functions, I can make the function bodies somewhat shorter.
foo :: MonadState AppStateRec m = m ()
foo = do st - get
put $ st { a = 1:(a st) }
foo :: MonadStateA m = m ()
foo = modifyA (1:)
bar :: MonadState AppStateRec m = m ()
bar = do st - get
put $ st { b = 2:(b st) }
bar :: MonadStateB m = m ()
bar = modifyB (2:)
At this point, you have several options. If you're willing to allow
undecidable instances, you can write instances like:
instance MonadState AppStateRec m = MonadStateA m
where getA = get = return . a
modifyA f = do st - get
put (st { a = f (a st) })
instance MonadState AppStateRec m = MonadStateB m
where getB = get = return . b
modifyB f = do st - get
put (st { b = f (b st) })
And the remainder of your code will run as you wrote it. An
alternative without using undecidable instances is to write the
instances manually. However, in that case, I believe you will have to
write your monad as a newtype instead of a type, and then rely on
either GHC's ability to derive instances of MonadState etc. or else
write those instances yourself as well.
Hope that helps.
/g
type Eval a = StateT AppStateRec Identity a
exec :: Eval ()
exec = do foo
bar
foo
foo
bar
go = runIdentity $ runStateT exec AppStateRec { a = [], b = [] }
Prints: ((),AppStateRec {a = [1,1,1], b = [2,2]})
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
It is myself I have never met, whose face is pasted on the underside of my mind.
___
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: Re: [Haskell-cafe] AT solution: rebinding = for restricted monads
On the FD impasse: Witness.hs:33:0: Couldn't match expected type `m'' (a rigid variable) against inferred type `RealWitness a a'' `m'' is bound by the type signature for `' at Witness.hs:11:29 When using functional dependencies to combine Witness WitnessReally a b (RealWitness a b), (and a screenful more) Any suggestions? What follows isn't so much a suggestion, but I think it's a description of this error's origins. Note that ='s signature from the class declaration class Witness w a b m | w a b - m, m - w a b where (=) :: (Witness w a a' m', Witness w a' b m'') = m' x - (x - m'' y) - m y () :: (Witness w a a' m', Witness w a' b m'') = m' x - m'' y - m y f g = f = const g private_return :: x - m x fail :: String - m x is copied to this instance declaration, instance Witness WitnessReally a b (RealWitness a b) where so we have: (=) :: ( Witness WitnessReally a a' m' , Witness WitnessReally a' b m'' ) = m' x - (x - m'' y) - (RealWitness a b) y Now consider what the signature of = for this instance would be if this copy from the class to the instance operation were savvy to our plans: (=) :: ( Witness WitnessReally a a' (RealWitness a a') , Witness WitnessReally a' b (RealWitness a' b) ) = (RealWitness a a') x - (x - (RealWitness a' b) y) - (RealWitness a b) y This signature is what the FD analyzer determines. Our above error arises because the actual signature of = has m' where the FDs indicate we'll always have (RealWitness a a'). Does that seem accurate? (I've put off actually looking at the GHC source for ages now...) In my opinion, this is reminiscent of some of the scoped-type variable issues and notions (e.g. wobbly types). By the functional dependency |w a b - m|, we know that the m' and m'' in the signature of = will be determined as some particular types (i.e. the class is a type function from w a b to m), and we'd just like to refer to whatever those types actually are as m' and m''. It seems the FD analyzer determines for us what those particular types are, but then the type-checker is unhappy that we're naming them m' and m'' when we should know more about them (e.g. that they have a RealWitness tycon). Unfortunately, we have no choice about the signature of = at the instance declaration, since it's copied straight from the class declaration. If m' and m'' were recognized as partially wobbly variables, then maybe this wouldn't be a problem. Or maybe wobbly types could be framed in terms of functional dependencies on a non-method's signature? (The rest might be off-topic.) This situation also conjures up some of my own confusion about FDs, the open world assumption, and finalizing a typeclass. One of my main confusions with FDs is how they play with the open world assumption. Another confusion is that just because your instance declarations satisfy the FDs of a class, they won't necessisarily allow the type inference engine to act in accord to those FDs. Sometimes you have to break a class's definition into ancillary classes, each with one of the FDs you want and appropriate instance declarations to drive the inference along those particular FDs. If you try to cram all of the FDs into one set of instance declarations, they tend to choke the FD analyzer. (I read FDs as a b and c determine x y and z; this is a description of the class's membership, but the FD analysis takes place on the instance declarations themselves and not necessarily the types admitted to the class.) Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type hackery question
[Sorry for the duplicate Jeff.] Is it possible to write a class which checks to see if two given type arguments are unifiable? This will probably help: http://www.haskell.org/pipermail/haskell-cafe/2006-November/019705.html That was Oleg's response to a post of mine: http://www.haskell.org/pipermail/haskell-cafe/2006-November/019610.html I find his code is much clearer and idiomatic, but it offers a little less control than mine (which kinda crosses the elegance boundary for type hackery with kinds and such). Hopefully you just need the Normalize type class. Happy hacking, Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: [Haskell-cafe] Composing monads (sort of)
Once I start needing to combine Maybe with other monads, I usually
take a moment to generalize the appropriate Maybe parts to MonadError
e m = m. Then we can just use the (ErrorT e IO) monad.
Nick
On 12/16/06, Pepe Iborra [EMAIL PROTECTED] wrote:
Wait, there are two monads in scene here, IO and Maybe.
The right solution is to compose them indeed. One could use the
MaybeT monad transformer defined in the 'All about monads' tutorial
[1], or we could just define the IOmaybe monad:
import Data.Traversable (mapM)
newtype IOMaybe a = IOM { iom :: IO (Maybe a) }
instance Monad IOMaybe where
return = IOM . return . Just
c = f = IOM$ do
mb_v - iom c
mapM (iom.f) mb_v = return . join
Now we can define:
t1 = IOM . return . f1
t2 = IOM . f2
t3 = IOM . return . f3
traverse rec1 = t1 rec1 = t2 = t3
And this scheme lends itself very well to define any kind of traversal.
Note that I used the more general version of mapM defined in
Data.Traversable in the definition of the (=) combinator. A more
conventional definition is given the 'All about monads' tutorial.
Cheers
pepe
1- http://www.nomaware.com/monads/html/index.html
On 16/12/2006, at 15:35, Chris Eidhof wrote:
Hey Mark,
How can I concisely compose these functions without having to
write a cascade of case statements such as:
case f1 rec1 of
Nothing - return Nothing
Just id1 - do
rec2 - f2 id2
return $ case rec2 of
Nothing - return Nothing
Just rec2' - case f3 rec2' of
I understand that if I was just dealing with Maybe I could use the
fact that Maybe is a monad.
Yes, you can write like this:
id2 - f1 rec1
rec2 - f2 id2
rec3 - f3 rec2
return rec3
or, even shorter:
id2 - f1 rec1
rec2 - f2 id2
f3 rec2
The cool thing of the Maybe monad is that it combines a result in
such a way that it removes the plumbing of constantly checking for
Nothing. I can definitely recommand you the following tutorials:
http://www.nomaware.com/monads/html/index.html
http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html
Those two tutorials really helped me.
Good luck,
Chris
___
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 mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: [Haskell-cafe] Building the community
On 12/14/06, Ross Paterson [EMAIL PROTECTED] wrote: Absolutely. Some more questions of this type: How do I update a variable? How can I efficiently update an array? How do I get debugging output? How can I put different types of things in a list? Sometimes the person asking is ready for the advanced features, but all too often beginners are pointed at IORefs, the ST monad, trace and existential types, when, as you say, they probably asked the wrong question because they don't have the frame of reference to know what they need. I've definitely made that mistake about the heterogenous list. I blurted out existential code when they just didn't know about data types. Sure I see the mistake I made there, but variant types are often assumed to have been ruled out--it's kind of step one with Haskell. That's not to say it was the poster's fault: any question is a good question. Sometimes it's appropriate to assume some knowledge on the poster's behalf, and it would be tedious if every first response was a list of 10 questions gauging the poster's familiarity with various intro topics. Brainstorming: 1) The first response to a FAQ should be a link to a thorough treatment of the FAQ on the wiki. Of course first responders ignorant of the wiki FAQ's existence wouldn't be able to do this, but if the community is consistent, then people will most likely catch on (I suddenly realize that I'm talking about myself...) 2) The welcome to the mailing list message could say if you're new to Haskell, please check this FAQ first. I'm talking big letters here; I'd even be OK with marquee. Are these rules too draconian? Should we just adopt the tedium of quizing every new poster? What are some other steps that could help prevent overly sophistocated first responses? Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] less than helpful GHC error message
Consider the terminal session at the bottom of this message.
The extra xc in Test.hs was the result of me missing CTRL during an
Emacs command (I'm guessing...). Unfortunately this took 30 minutes to
find since I had far more than two modules and the error message
doesn't point this out. Sure it's a silly mistake to make, but I'm
guessing it's pretty common.
I'm running GHC 6.6 on a PPC Mac.
I know pragmas are wierd things, but could this error message be improved?
Thanks,
Nick
$ head -n 1 Main.hs Test.hs
== Main.hs ==
module Main where
import Test
main = test
== Test.hs ==
xc{-# OPTIONS -fglasgow-exts #-}
module Test where
test = putStrLn weee
$ ghc --make Main
no location info: file name does not match module name `Main'
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] type variable question
I'm developing a typesafe record library (akin to HList but starting with key/val pairs and enforcing uniqueness and sorted order of keys). I'm having a GHC problem I've had with other projects and seen comments regarding it in other people's code (HList for instance: GHC doesn't like it's own type to paraphrase). I have a function |update| --update :: forall sel val rec val' rec' . -- SetField sel val rec val' rec' = sel - (val - val') - rec - rec' update sel f rec = rec' where --val :: val val = value sel rec --val' :: val' val' = f val --rec' :: rec' rec' = set sel val' rec 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. I don't plan on sharing the code for |SetField| because it's that wild looking type class hackery, and the problem isn't specific to this example--I remember having it happen in far simpler cases which I can't seem to find right now... Is there a canonical example example that exhibits this behavior? Or a ticket for it already? I'd like to understand what's happening. Thanks for your time, Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stratified monads
As far as I know, the stratified monads are recognized as monad transformers in Haskell. The predominant library is the Monad Transformer Library (or mtl) coded by Andy Gill, see [1]. One of my favorite examples of the usefulness of monad transformers is for building domains for denotational semantics: see [2]. I'm sure other people can sugget many other favorite uses. I hope I haven't misinterpreted stratified monads... Nick [1] - http://www.haskell.org/ghc/docs/latest/html/libraries [2] - http://citeseer.ist.psu.edu/liang95monad.html On 12/11/06, Mark T.B. Carroll [EMAIL PROTECTED] wrote: I was interested to read David Espinosa's Stratified Monads paper at http://www-swiss.ai.mit.edu/~dae/papers/sm.ps.Z I'm not sure I actually understand them properly yet, but I'm already curious about if anybody's played with them in Haskell, or how useful it would be to do so. Any comments? -- Mark ___ 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: Re: Re: [Haskell-cafe] Writing Haskell For Dummies Or At Least For People Who Feel Like Dummies When They See The Word 'Monad'
I have taken the liberty to read into the definition of practical Haskell; if I'm off target let me know so I can tweak my claims to fit whatever it is I thought I was discussing ;). Two cents: 1) This wouldn't be the first book introducing functional programming to imperative programmers. It would seem wise to investigate existing literature and see how the good ones handled that: which examples, when to introduce what, etc. The purity issue probably will be a novelty to a Haskell book though. 2) This wouldn't be the first book introducing Haskell to functional programmers. It would seem wise to investigate existing literature... I've read (and heard) a lot of claims that the existing learn Haskell books don't teach you real Haskell. I believe it's because the existing books tackle both 1 and 2 above, leaving no room for 3) This would be the first book introducing the nuances of large systems development in Haskell to Haskell programmers. Explaining well various monads (e.g. how to use mtl), or other things necessary for practical Haskell (e.g. ByteString, database interface, web app, parsing, and many other systems libraries), requires of the audience a rather thorough understanding of Haskell's type system (MPTC and other extensions for mirth). In summary: If this is to be a reasonably sized book, then I think it must assume some working knowledge of Haskell. There are a number of good books to learn the basics, but there doesn't seem to be a standard read this book for Haskell systems development. Eschew the basics to make room for the good stuff. If this is not to be a reasonably sized book (i.e. it will go from knowing Haskell 0% all the way to writing real world programs), then I think the good existing literature should be the inspiration for the learn Haskell section. I love the analogies as much as the next programming languages researcher, but I think introducing Haskell in text has been done and done well--it doesn't need a new approach. So don't reinvent the learn Haskell text; that way you can spend time on the good stuff. Nick ps - I'd be happy to participate in varying degrees with any collaborative effort. On 12/11/06, Kirsten Chevalier [EMAIL PROTECTED] wrote: On 12/11/06, Matt Revelle [EMAIL PROTECTED] wrote: What do you mean by real publisher? As long as the quality of the final product is good, does it really matter what publishing company has their name stamped on it? It matters to me; if I'm going to put work into this, then that's what I want the result to be. I'm happy, of course, for projects that I am not involved in to use whatever publishing mechanisms that the people involved in those projects prefer. If you want to help with the writing project that I have in mind, then discuss that on the list. If you want to start another writing project whose primary goal is to produce an open-content, electronic book, then announce that on the list too. If you want to debate the merits of open-content versus traditional publishing, well, I'd love to have that debate too, but this list probably isn't the right forum for that. Cheers, Kirsten -- Kirsten Chevalier* [EMAIL PROTECTED] *Often in error, never in doubt There are many places in computer science where it's actually helpful to procrastinate. -- Eric Brewer ___ 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: Re: [Haskell-cafe] Cannot understand liftM2
The interpreter infers that m = (e -) because of the types of snd and fst.
When snd and fst are considered as monadic computations in the (e -)
monad, there types are:
Prelude :t fst
fst :: (a, b) - a
Prelude :t snd
snd :: (a, b) - b
Note that: (a, b) - a =~= m awhere m x = (a,b) - x
So if we apply liftM2 to fst and snd, then the m of the result has to
be the same as the m of the arguments; thus the m of the result is
((a, b) -). Now the type of (-) is:
Prelude :t (-)
(-) :: (Num a) = a - a - a
Thus the interpreter knows that the a and b in the ((a, b) -) monad
are actually the same. Finally we have:
Prelude Control.Monad.Reader :t liftM2 (-) snd fst
liftM2 (-) snd fst :: (Num a) = (a, a) - a
Note that: (a, a) - a =~= m awhere m x = (a,a) - x
So each argument to liftM2 contributes constraints to the components
of liftM2's general type:
Prelude :t liftM2
liftM2 :: (Monad m) = (a1 - a2 - r) - m a1 - m a2 - m r
snd forces m to be ((x,a2) -)
fst forces m to be ((a1,y) -)
(-) forces a1 and a2 to be the same
The conjunction of these contraints forces {a1:=a, a2:=a, m:=(a,a) -}.
HTH,
Nick
On 12/11/06, Nicola Paolucci [EMAIL PROTECTED] wrote:
Hi All, Hi Cale,
Can you tell me if I understood things right ? Please see below ...
On 12/11/06, Cale Gibbard [EMAIL PROTECTED] wrote:
The monad instance which is being used here is the instance for ((-)
e) -- that is, functions from a fixed type e form a monad.
So in this case:
liftM2 :: (a1 - a2 - r) - (e - a1) - (e - a2) - (e - r)
I bet you can guess what this does just by contemplating the type. (If
it's not automatic, then it's good exercise) Now, why does it do that?
So the way I have to reason on the output I get from ghci is:
Prelude :t liftM2
liftM2 :: (Monad m) = (a1 - a2 - r) - m a1 - m a2 - m r
The m stands for ((-) e), that is like writing (e - a1): a function
which will take an argument of type e and will return an argument of
type a1.
And so the above line has a signature that reads something like:
liftM2 will takes 3 arguments:
- a function (-) that takes two arguments and returns one result of type r.
- a function (fst) that takes one argument and returns one result.
- a function (snd) that takes one argument and returns one result.
- the result will be a certain function that will return the same type
r of the (-) function.
- Overall to this liftM2 I will actually pass two values of type a1
and a2 and will get a result of type r.
From the type signature - correct me if I am wrong - I cannot actually
tell that liftM2 will apply (-) to the rest of the expression, I can
only make a guess. I mean I know it now that you showed me:
liftM2 f x y = do
u - x
v - y
return (f u v)
If this is correct and it all makes sense, my next question is:
- How do I know - or how does the interpreter know - that the m of
this example is an instance of type ((-) e) ?
- Is it always like that for liftM2 ? Or is it like that only because
I used the function (-) ?
I am trying to understand this bit by bit I am sorry if this is either
very basic and easy stuff, or if all I wrote is completely wrong and I
did not understand anything. :D Feedback welcome.
Thanks again,
Regards,
Nick
___
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: Re: [Haskell-cafe] interval arithmetic for integers?
I did see that one on the wiki; but it doesn't seem to support the open intervals (i.e. (-inf, 3)) and I'd really like those. That is the leading candidate right now though... There was also this one: http://www.dinkla.net/fp/cglib.html It mentions rangetrees but I'm not sure if that's the kind I'm thinking of. That package has what seems like scary math. Thanks, Nick On 12/8/06, Taral [EMAIL PROTECTED] wrote: Some of that is in the Ranged Sets library: http://ranged-sets.sourceforge.net/Ranged/ but it doesn't support Num. On 12/8/06, Nicolas Frisby [EMAIL PROTECTED] wrote: I'm looking to not reinvent the wheel. Is there an existing package that supports interval arithmetic on integers (or more)? A possible complication is that I'm hoping to include open intervals such as (GreaterEqThan 3). -- Taral [EMAIL PROTECTED] You can't prove anything. -- Gödel's Incompetence Theorem ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: Re: [Haskell-cafe] interval arithmetic for integers?
Fantastic! Just another bit of evidence that Haskell Cafe + one night's sleep can save a great deal of work. :) Thanks for pointing that out, Nick On 12/8/06, Taral [EMAIL PROTECTED] wrote: On 12/8/06, Nicolas Frisby [EMAIL PROTECTED] wrote: I did see that one on the wiki; but it doesn't seem to support the open intervals (i.e. (-inf, 3)) and I'd really like those. Oh, it does. See BoundaryAboveAll and BoundaryBelowAll. -- Taral [EMAIL PROTECTED] You can't prove anything. -- Gödel's Incompetence Theorem ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] interval arithmetic for integers?
I'm looking to not reinvent the wheel. Is there an existing package that supports interval arithmetic on integers (or more)? A possible complication is that I'm hoping to include open intervals such as (GreaterEqThan 3). If there's not a package to go with, any pointers on the appopriate rules for this stuff? I started coding up multiplication and decided it was harder than I first thought... Thanks for your time, Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (a - [b]) - [a - b] ?
It seems there's an assumption about the range of the parameter function and the range of the entire function. That is, I think we're assuming that the length of the final result is the same as the length of the result of the first function? If I'm correct in presuming that constraint, then I think this indicates that a more elegant solution might involve using the lightweight-dependently-typed vectors approach. Though I can't promise it will actually be nicer! Nick On 12/4/06, Joachim Breitner [EMAIL PROTECTED] wrote: Hi, while pondering over the four fours problem, I wondered: Is there a function of type (a - [b]) - [a - b] It looks a bit like sequence when applied in the ((-) a) Monad: sequence :: [a - b] - a - [b] but I was looking for the other direction. I came up with: \g - map (\n a - g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas? Thanks, Joachim -- Joachim nomeata Breitner mail: [EMAIL PROTECTED] | ICQ# 74513189 | GPG-Key: 4743206C JID: [EMAIL PROTECTED] | http://www.joachim-breitner.de/ Debian Developer: [EMAIL PROTECTED] ___ 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: Re: [Haskell-cafe] Parsec: Where's +++?
A agreed upon technique for dealing with typeclass hierarchies has
been slow to arrive. For instance, all monads are functors, but
providing a monad instance for your type doesn't automatically make it
a functor as well.
All monads are also applicative functors, and Control.Applicative does
have a newtype to recognize them as such:
Prelude :m + Control.Applicative
Prelude Control.Applicative :i WrapMonad
newtype WrappedMonad m a = WrapMonad {unwrapMonad :: m a}
-- Defined in Control.Applicative
Prelude Control.Applicative :i Applicative
class (Functor f) = Applicative f where
pure :: a - f a
(*) :: f (a - b) - f a - f b
-- Defined in Control.Applicative
instance (Monad m) = Applicative (WrappedMonad m)
-- Defined in Control.Applicative
...
Just wrap up your monad in WrapMonad, treat it like an applicative
functor, and then unwrap it with unwrapMonad.
HTH,
Nick
On 12/1/06, Greg Fitzgerald [EMAIL PROTECTED] wrote:
Text.ParserCombinators.ReadP.(+++) :: ReadP a - ReadP a - ReadP a
Wow, fast and complete, Thanks Don!:)
Would it make sense to derive instances of Applicable and Alternative
for ReadP? Something like this maybe:
instance Applicative ReadP where
pure = return
(*) = ap
instance Alternative ReadP where
empty = pfail
(|) = (++)
Thanks,
Greg
___
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] haddock infix questions
I found nothing in the Gmane archives, so I turn to you. I'm hoping to Haddock-a-chop my library but the ole infix type constructor (and there are many of them) is causing a parse error. It seems a common enough problem, so I was wondering... 1) What ended up happening with David Waern's SoC project? I tried the darcs repo at http://darcs.haskell.org/SoC/haddock.ghc/, but got some error messages that I think indicate I don't have an appropriate GHC As a Library package (`HsDoc' not in scope). I'm running GHC 6.6 on a Mac. I'll avoid a manual build of a snapshot GHC until it's my last option, so I haven't made strides to check if HsDoc is actually in the dev GHC repo. 2) Is there a good workaround out there for such a parse error? I'm thinking someone might have a handy pre-processor to help out Haddock? Thanks for your time, Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: [Haskell-cafe] Collection of objects?
Depending on your needs and your comfort level with fancier types, the
existential approach to ADTs might solve your problem. The following
code is a demonstration you can cut-and-paste-and-run.
This is example akin to upcasting in Java to an interface that lets
you print things. That way you know how to print every object (or do
whatever else it is you need to do) in the list. Beware: there is no
safe downcasting (that's what Typeable would be for); that would
likely be more than you need.
There are other ways to do this with existentials (e.g. bounded
existentials), but this is what came out of my head when I read your
post. Existentials seems to be the Haskellish way to reduce a
hetergenous list to a collection of objects with common operations.
HList would be the Haskellish way for more static and flexible
assurances.
{-# OPTIONS -fglasgow-exts #-}
module Test where
data PrintPackage = forall a . PrintPackage a (a - String)
instance Show PrintPackage where
show (PrintPackage val showMethod) = showMethod val
list = [ PrintPackage 3 show
, PrintPackage string show
, PrintPackage 3.4 show
]
main = print list
Hope that helps more than it confuses,
Nick
On 11/17/06, Henning Thielemann [EMAIL PROTECTED] wrote:
On Fri, 17 Nov 2006, Valentin Gjorgjioski wrote:
Is some kind of collection of object with different types in Haskell exist?
Except the tuples, which have fixed length.
I find this
* Tuples heterogeneous, lists homogeneous.
* Tuples have a fixed length, or at least their length is encoded in
their type. That is, two tuples with different lengths will have
different types.
* Tuples always finite.
But I need something which is heterogeneous and non-fixed length. I'm used do
Java, and this switch to functional languages is very strange to me. So, to be
clear, I need something like LinkedListObject in java.
Can you please help me or suggest me, what can I use in this case?
If the number of types to cover is fixed, then I suggest a data type like
data T =
ConsIntInt
| ConsString String
| ConsChar Char
Since this is a very FAQ I wonder why I don't find the answer in any of
the Haskell wikis.
___
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
