[Haskell-cafe] databases in Haskell type-safety
Hi! I'd like to use sqlite3 as application storage in my haskell project... Browsing the available database options in Haskell it seems that: a) HSQL is dead (hackage reports build-failure with 6.8 6.10) b) haskelldb is also not in a good shape - build fails with 6.8 6.10 For Haskell-newbie as myself, it looks that haskelldb is the one which provide(ed)s the most secure API (I was reading draft paper about MetaHDBC but, apparently, the type inference support in open-source databases is poor and that's why, according to the author This is unfortunately as it makes MetaHDBC a lot less valuable. What remains is: c) Takusen which is also not up-to-date (it fails with 6.10) and d) HDBC and sqlite bindings which are the only packages which build with 6.10. However options in d) do not offer, afaik, type-safety which is emblem of Haskell language, so I wonder how much this could be the problem for real-world usage? So, considering that HDBC nicely abstracts API enabling one to easily switch from e.g. Sqlite3 to Postgres, and it is used as in example for database programming, it seems as logical (and the only) choice for Haskell database programming in a real-world? I'm not familiar with Takusen which says: Takusen's unique selling point is safety and efficiency... and I would appreciate if someone could shed some more light to its 'safety' and the present status? Sincerely, Gour -- Gour | Zagreb, Croatia | GPG key: C6E7162D pgpECYShrDstY.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Updating doubly linked lists
Stephan Guenther wrote:
Is it possible to change a particular node of the doubly linked list?
That is to say, that would like to have a function:
update :: DList a - a - DList a
where
update node newValue
returns a list where only the value at the node which is passed in is
set to the new Value and all other values are the same. All this of
course in a pure way, that is without using (M/T/TM)Vars or IORefs.
It is possible to do all of this, and more:
- no rebuilding of the whole list on updates to the list
- the update operation takes constant time (for lists longer
than 32 elements on 32-bit platform)
- both cyclic and terminated lists can be handled, uniformly
- no monads used or mentioned
- let alone no IORef, STRef, TVars, etc.
The algorithm is essentially imperative (and so permits identity
checking and in-place `updates') but implemented purely
functionally. No destructive updates are ever used. Therefore, all the
changes can be undone and re-done, and the code is MT-safe. The code
is easily generalizable to 2D.
Here are the tests
testl = fromList [1..5]
testl_s = takeDL 11 testl
*FL testl_s
[5,1,2,3,4,5,1,2,3,4,5]
testl1 = update (-1) testl
testl1_s = takeDL 11 testl1
*FL testl1_s
[-1,1,2,3,4,-1,1,2,3,4,-1]
testl2 = update (-2) . move_right' . move_right' $ testl1
testl2_s = takeDL 11 testl2
*FL testl2_s
[-2,3,4,-1,1,-2,3,4,-1,1,-2]
-- Old testl is still available
testl3 = update (-2) . move_right' . move_right' $ testl
testl3_s = takeDL 11 testl3
*FL testl3_s
[-2,3,4,5,1,-2,3,4,5,1,-2]
It is not for nothing Haskell is called the best imperative
language. One can implement imperative algorithms just as they are --
purely functionally, without any monads or other categorical notions.
module FL where
import qualified Data.IntMap as IM
-- Representation of the double-linked list
type Ref = Int -- positive, we shall treat 0 specially
data Node a = Node{node_val :: a,
node_left :: Ref,
node_right :: Ref}
data DList a = DList{dl_counter :: Ref, -- to generate new Refs
dl_current :: Ref, -- current node
dl_mem :: IM.IntMap (Node a)} -- main `memory'
-- Operations on the DList a
empty :: DList a
empty = DList{dl_counter = 1, dl_current = 0, dl_mem = IM.empty}
-- In a well-formed list, dl_current must point to a valid node
-- All operations below preserve well-formedness
well_formed :: DList a - Bool
well_formed dl | IM.null (dl_mem dl) = dl_current dl == 0
well_formed dl = IM.member (dl_current dl) (dl_mem dl)
is_empty :: DList a - Bool
is_empty dl = IM.null (dl_mem dl)
-- auxiliary function
get_curr_node :: DList a - Node a
get_curr_node DList{dl_current=curr,dl_mem=mem} =
maybe (error not well-formed) id $ IM.lookup curr mem
-- The insert operation below makes a cyclic list
-- The other operations don't care
-- Insert to the right of the current element, if any
-- Return the DL where the inserted node is the current one
insert_right :: a - DList a - DList a
insert_right x dl | is_empty dl =
let ref = dl_counter dl
-- the following makes the list cyclic
node = Node{node_val = x, node_left = ref, node_right = ref}
in DList{dl_counter = succ ref,
dl_current = ref,
dl_mem = IM.insert ref node (dl_mem dl)}
insert_right x d...@dlist{dl_counter = ref, dl_current = curr, dl_mem = mem} =
DList{dl_counter = succ ref, dl_current = ref,
dl_mem = IM.insert ref new_node $ IM.insert curr curr_node' mem}
where
curr_node = get_curr_node dl
curr_node'= curr_node{node_right = ref}
new_node = Node{node_val = x, node_left = curr,
node_right = node_right curr_node}
get_curr :: DList a - a
get_curr = node_val . get_curr_node
move_right :: DList a - Maybe (DList a)
move_right dl = if next == 0 then Nothing else Just (dl{dl_current=next})
where
next = node_right $ get_curr_node dl
-- If no right, just stay inplace
move_right' :: DList a - DList a
move_right' dl = maybe dl id $ move_right dl
fromList :: [a] - DList a
fromList = foldl (flip insert_right) FL.empty
takeDL :: Int - DList a - [a]
takeDL 0 _ = []
takeDL n dl | is_empty dl = []
takeDL n dl = get_curr dl : (maybe [] (takeDL (pred n)) $ move_right dl)
-- Update the current node
update :: a - DList a - DList a
update x dl@(DList{dl_current = curr, dl_mem = mem}) =
dl{dl_mem = IM.insert curr (curr_node{node_val = x}) mem}
where
curr_node = get_curr_node dl
testl = fromList [1..5]
testl_s = takeDL 11 testl
testl1 = update (-1) testl
testl1_s = takeDL 11 testl1
testl2 = update (-2) . move_right' . move_right' $ testl1
testl2_s = takeDL 11 testl2
-- Old testl is still available
testl3 = update (-2) . move_right' . move_right' $ testl
testl3_s = takeDL 11 testl3
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
Re: [Haskell-cafe] databases in Haskell type-safety
Excerpts from Gour's message of Sat Jan 03 03:48:44 -0600 2009: Hi! I'd like to use sqlite3 as application storage in my haskell project... Browsing the available database options in Haskell it seems that: a) HSQL is dead (hackage reports build-failure with 6.8 6.10) b) haskelldb is also not in a good shape - build fails with 6.8 6.10 For Haskell-newbie as myself, it looks that haskelldb is the one which provide(ed)s the most secure API (I was reading draft paper about MetaHDBC but, apparently, the type inference support in open-source databases is poor and that's why, according to the author This is unfortunately as it makes MetaHDBC a lot less valuable. What remains is: c) Takusen which is also not up-to-date (it fails with 6.10) and d) HDBC and sqlite bindings which are the only packages which build with 6.10. Have you tried the simple sqlite3 bindings available? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sqlite I'm not familiar with Takusen which says: Takusen's unique selling point is safety and efficiency... and I would appreciate if someone could shed some more light to its 'safety' and the present status? Takusen is based on the (unique) concept of a left-fold enumerator. Having a left-fold interface guarantees timely (nearly perfect, really) deallocation of resources while still having the benefits of a 'lazy' stream. This interface has (as shown by Oleg and others) proven to be very efficient in a number of cases as well as favorable for many. The idea is very novel, and truly worth exploring if you ask me. For more information about left-fold enumerators and takusen, see here: http://okmij.org/ftp/papers/LL3-collections-enumerators.txt http://okmij.org/ftp/Haskell/fold-stream.lhs http://okmij.org/ftp/Haskell/misc.html#takusen NB: I have *just* (about 5 minutes ago) sent in a patch for takusen to get it to build on GHC 6.10.1 to Oleg. Hopefully an updated version will appear on hackage in the next few days. Austin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unsafeInterleaveIO respecting order of actions
On Thu, 1 Jan 2009, Brandon S. Allbery KF8NH wrote: On 2009 Jan 1, at 16:44, Henning Thielemann wrote: If it is generally possible to use unsafeInterleaveIO such that it executes actions in the right order, wouldn't this allow the definition of a general lazy IO monad? I thought unsafeInterleaveIO and users of it (readFile, hGetContents) didn't guarantee the order of actions relative to independent IO actions (that is, those performed outside the unsafeInterleaveIO) and this was why it is generally disrecommended. For example the recurring situation where people try to readFile f = writeFile . someTransform and the writeFile fails with a file locked exception. Sure, it's dangerous. But for what I want to do, this situation cannot occur. I can come up with a simple example which might be generalized. It simulates what hGetContents does. liftLazy2 :: (a - b - c) - IO a - IO b - IO c liftLazy2 f x y = fmap (\ ~(xr, ~(yr,())) - f xr yr) $ unsafeInterleaveIO $ liftM2 (,) x $ unsafeInterleaveIO $ liftM2 (,) y $ return () test0, test1 :: IO String test0 = liftLazy2 (const) getLine getLine test1 = liftLazy2 (flip const) getLine getLine test0 only requests the first line, test1 expects two lines as user input. However, with liftLazy2 we have only Applicative functionality, not Monad, and it is not composable. For example: fmap (\((x,y),z) - z) $ liftLazy2A (,) (liftLazy2A (,) getLine getLine) getLine This requests only one line, but should three ones. The reason is that the first two getLines are defered even until the last one. Thus, it is not enough that liftLazy2 returns (IO c). Instead it must return (IO (c,(a,(b,() and these pair emulated lists must somehow be combined in order to preserve the order of execution. This looks somehow like a writer monad transformer. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Updating doubly linked lists
S. Günther wrote: What kind of structure do you need exactly? What I really need is a structure which represents a two dimensional grid, i.e. it consists of nodes having a value and a list of neighbours attached to it. Point is that if node 1 has node 2 as a neighbour then node 2 has to have node 1 as a neighbour and each node has the same number of neighbours (currently 4, but may vary). Ah, so you have a rectangular (or later hexagonal?) 2D grid? I suggest representing it as Data.Map (Integer, Integer) a as explained below. That's why I said that thinking about the circular case was just a divergence that really got me wondering/interested which is why I posted the question in it's short form at the beginning. Exploring a related easier problem is always a good way to get some intuition for tackling the harder one. :) Anyways, back to the structure I need. One additional thing which will happen during the algorithm is that there will be updates to a certain local neighboruhood of a node. Now I understand, that that might very well be possible with zippers. Instead of lists of neighbouring nodes I might as well save the paths through the graphs separately from the nodes although I only have a very vague intuition about how that would look like. And instead of calculating a lists of nodes to update, I could calculate a path visting the nodes and update them (again beeing unable to escape from the prison of an imperative mindset) traversing the path. A zipper indeed allows you to move to neighbors and update them. But the point was that I just had a hard time generalizing what I read about zippers to structures where you can have embedded cycles, e.g. up . left . down . right = id. If you interpret zippers as the original data structure with a hole, this is not so difficult. For instance, consider a rectangular grid +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ where you store some data at every node. Now, a zipper is just the old data structure but one node is marked as hole +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--O--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ If you represent the grid as a rectangular table type Position = (Integer, Integer) type Grid a = Data.Map Position a a zipper is simply the grid with an extra marker type Zipper a = (Grid a, Position) left,right,up,down :: Zipper a - Zipper a left (g,(x,y)) = (g,(x-1,y)) right (g,(x,y)) = (g,(x+1,y)) up(g,(x,y)) = (g,(x,y-1)) down (g,(x,y)) = (g,(x,y+1)) update :: a - Zipper a - Zipper a update a (g,(x,y)) = (insert (x,y) a g, (x,y)) Note that the left, right etc. are not baked into the data type but implemented as normal functions. In principle, the same could be done for lists type ZipperL a = ([a], Int) left, right :: ZipperL a - ZipperL a left (xs,i) = (xs,i-1) right (xs,i) = (xs,i+1) update :: a - ZipperL a - ZipperL a update a (xs,i) = (take i xs ++ [a] ++ drop (i+1) xs, i) This is a valid implementation of a zipper for lists, but of course is very inefficient, update is O(n) . The key thing about the original list zipper with back and front list is that all operations are O(1). For the 2D grid zipper above, moving around is O(1) but update is O(log n). This is acceptable; also because I'm quite confident that a zipper for a 2D grid with everything O(1) does not exist. I can prove that for a special case and should probably write it down at some point. In other words, I suggest representing your grid as a Data.Map (Integer,Integer) a and accept the minor inconvenience of a O(log n) update. Choosing a different finite map implementation may give a better constant factor. For instance you can nest two Data.IntMap etc. Righty right, but there's still the possibility that given all the time in the world and the clearest explanations I'm just to dense to get a hold of it. That said I hope that's not the case but I might still be better off timewise to just go with MVars and a straightforward way first and then doing the reading and maybe refactoring to a different approach. My personal experience is that not going with the obvious but messy solution but searching for a more elegant one is always faster in the long run. :) Regards, H. Apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] databases in Haskell type-safety
Gour schrieb: Hi! I'd like to use sqlite3 as application storage in my haskell project... Browsing the available database options in Haskell it seems that: a) HSQL is dead (hackage reports build-failure with 6.8 6.10) No, it is maintained by frede...@ofb.net . I have also contributed Oracle/OCI code a half year ago. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: databases in Haskell type-safety
Henning == schlepp...@henning-thielemann.de writes: Henning No, it is maintained by frede...@ofb.net . I have also Henning contributed Oracle/OCI code a half year ago. Oops, I stand corrected...nice to hear. Still, it would be nice to present some info 'cause web site still shows 1.7 from Dec '05 as the latest release :-( Sincerely, Gour -- Gour | Zagreb, Croatia | GPG key: C6E7162D pgpb32PgU4X2z.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: databases in Haskell type-safety
Austin == Austin Seipp mad@gmail.com writes: Austin Have you tried the simple sqlite3 bindings available? Austin http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sqlite Not (yet), but those are the one I mentioned (besides HDBC) under d) ;) Austin Takusen is based on the (unique) concept of a left-fold Austin enumerator. Having a left-fold interface guarantees timely Austin (nearly perfect, really) deallocation of resources while still Austin having the benefits of a 'lazy' stream. This interface has (as Austin shown by Oleg and others) proven to be very efficient in a Austin number of cases as well as favorable for many. The idea is very Austin novel, and truly worth exploring if you ask me. Thank you very much. I went through the docs for which you provided some references - I cannot claim I understood everything, but it sounds/looks quite interesting and worth exploring. Is there any simple tutorial about using Takusen available somewhere? Austin NB: I have *just* (about 5 minutes ago) sent in a patch for Austin takusen to get it to build on GHC 6.10.1 to Oleg. Hopefully an Austin updated version will appear on hackage in the next few days. Great news! Sincerely, Gour -- Gour | Zagreb, Croatia | GPG key: C6E7162D pgpWbjHPU1bkV.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Updating doubly linked lists
Is it possible to change a particular node of the doubly linked list? That is to say, that would like to have a function: update :: DList a - a - DList a where update node newValue returns a list where only the value at the node which is passed in is set to the new Value and all other values are the same. What you need is for the nodes to keep track of the length of the list. Here's a different solution from that oleg posted, to me it's slightly more intuitive, since the updates work directly on the dlists instead of via (elegant) proxy functions. -- module DList where data DList a = DNode Int (DList a) a (DList a) | Empty mkDList :: [a] - DList a mkDList [] = Empty mkDList xs = let len = length xs this = DNode len farLeft (head xs) nearRight (nearRight,farLeft) = mkRestDList len (tail xs) this this in this mkRestDList :: Int - [a] - DList a - DList a - (DList a, DList a) mkRestDList _ [] _ farRight = (farRight, farRight) -- will only happen if the initial list is singleton mkRestDList len [x] nearLeft farRight = let this = DNode len nearLeft x farRight in (this, this) mkRestDList len (x:xs) nearLeft farRight = let this = DNode len nearLeft x nearRight (nearRight,farLeft) = mkRestDList len xs this farRight in (this,farLeft) takeD :: Int - DList a - [a] takeD 0 _ = [] takeD _ Empty = [] takeD n (DNode _ _ x r) = x : takeD (n-1) r leftD, rightD :: DList a - DList a leftD Empty = Empty leftD (DNode _ l _ _) = l rightD Empty = Empty rightD (DNode _ _ _ r) = r updateD :: a - DList a - DList a updateD _ Empty = Empty updateD x (DNode len _ _ r) = let this = DNode len farLeft x nearRight (nearRight,farLeft) = updateRestD (len-1) r this this in this updateRestD :: Int - DList a - DList a - DList a - (DList a, DList a) updateRestD 0 _ _ farRight = (farRight, farRight) -- will only happen if the initial list is singleton updateRestD 1 (DNode len _ x _) nearLeft farRight = let this = DNode len nearLeft x farRight in (this, this) updateRestD n (DNode len _ x r) nearLeft farRight = let this = DNode len nearLeft x nearRight (nearRight,farLeft) = updateRestD (n-1) r this farRight in (this,farLeft) updateRestD _ Empty _ _ = undefined -- can't happen - *DList let dl = mkDList [1..5] *DList takeD 11 dl [1,2,3,4,5,1,2,3,4,5,1] *DList let dl' = updateD (-1) dl *DList takeD 11 dl' [-1,2,3,4,5,-1,2,3,4,5,-1] Cheers, /Niklas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unsafeInterleaveIO respecting order of actions
On Sat, 3 Jan 2009, Henning Thielemann wrote: On Thu, 1 Jan 2009, Brandon S. Allbery KF8NH wrote: On 2009 Jan 1, at 16:44, Henning Thielemann wrote: If it is generally possible to use unsafeInterleaveIO such that it executes actions in the right order, wouldn't this allow the definition of a general lazy IO monad? I thought unsafeInterleaveIO and users of it (readFile, hGetContents) didn't guarantee the order of actions relative to independent IO actions (that is, those performed outside the unsafeInterleaveIO) and this was why it is generally disrecommended. For example the recurring situation where people try to readFile f = writeFile . someTransform and the writeFile fails with a file locked exception. Sure, it's dangerous. But for what I want to do, this situation cannot occur. I can come up with a simple example which might be generalized. It simulates what hGetContents does. liftLazy2 :: (a - b - c) - IO a - IO b - IO c liftLazy2 f x y = fmap (\ ~(xr, ~(yr,())) - f xr yr) $ unsafeInterleaveIO $ liftM2 (,) x $ unsafeInterleaveIO $ liftM2 (,) y $ return () I think I now have general Applicative functionality: apply :: (a - b, ()) - (a,()) - (b,()) apply (f,fs) a = let (a0,as) = case fs of () - a in (f a0, as) lazyIO :: IO a - IO (a,()) lazyIO = unsafeInterleaveIO . fmap (\x - (x,())) liftLazy2 :: (a - b - c) - IO a - IO b - IO c liftLazy2 f x y = liftM2 (\xr yr - fst $ (f,()) `apply` xr `apply` yr) (lazyIO x) (lazyIO y) The () is used to enforce the order of evaluation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: How do we decide on the new logo?
Achim Schneider wrote: ... Step 3: Re-open contest, accepting submissions _using_ the winning logo, in the categories a) colour schemes[1] b), official shapes[2] c), font[3] to go to b), d) layouts of b) + c) ... This is a good suggestion. I would like small adjustments to the logo to be possible before it's frozen. Some kind of Step 3 will result in a much better logo. For example, I really like the pyramid from above / square containing three triangles that Lenny222 submitted, but I wouldn't choose this precise colour scheme and form. I didn't have time to enter an alternative. When the field has been significantly reduced I think people will be willing to expend effort improving the remaining entries. Richard. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type Family Relations
Cafe, I am wondering if there is a way to enforce compile time checking of an axiom relating two separate type families. Mandatory contrived example: type family AddressOf h type family HeaderOf a -- I'm looking for something to the effect of: type axiom HeaderOf (AddressOf x) ~ x -- Valid: type instance AddressOf IPv4Header = IPv4 type instance HeaderOf IPv4 = IPv4Header -- Invalid type instance AddressOf AppHeader = AppAddress type instance HeaderOf AppAddress = [AppHeader] So this is a universally enforced type equivalence. The stipulation could be arbitrarily complex, checked at compile time, and must hold for all instances of either type family. Am I making this too hard? Is there already a solution I'm missing? Cheers, Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How to check object's identity?
Hi,
I tried this in ghci:
Prelude 1:2:[] == 1:2:[]
True
Does this mean (:) return the same object on same input, or
(==) is not for identity checking? If the later is true, how
can I check two object is the *same* object?
Thanks
Jan
--
jan=callcc{|jan|jan};jan.call(jan)
pgpJa3i8YUIrV.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: How to check object's identity?
Hi Jan, in functional programming there is no such thing as identity as we understand the idea from OO. There is only such as thing as equality though. Günther Am 03.01.2009, 16:28 Uhr, schrieb Xie Hanjian jan.h@gmail.com: Hi, I tried this in ghci: Prelude 1:2:[] == 1:2:[] True Does this mean (:) return the same object on same input, or (==) is not for identity checking? If the later is true, how can I check two object is the *same* object? Thanks Jan -- Erstellt mit Operas revolutionärem E-Mail-Modul: http://www.opera.com/mail/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to check object's identity?
Thanks guys :-)
* Nicolas Pouillard nicolas.pouill...@gmail.com [2009-01-03 16:39:59 +0100]:
Excerpts from Xie Hanjian's message of Sat Jan 03 16:28:30 +0100 2009:
Hi,
I tried this in ghci:
Prelude 1:2:[] == 1:2:[]
True
Does this mean (:) return the same object on same input, or
(==) is not for identity checking? If the later is true, how
can I check two object is the *same* object?
Here (==) is the structural equality. There is generally no exposed function
to check for identity of values. This would expose too much of the memory
model and the compilation process to give a specification to such a function.
--
Nicolas Pouillard
--
jan=callcc{|jan|jan};jan.call(jan)
pgpgPJ9sBZB8C.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] databases in Haskell type-safety
On Sat, Jan 3, 2009 at 4:25 AM, Austin Seipp mad@gmail.com wrote: NB: I have *just* (about 5 minutes ago) sent in a patch for takusen to get it to build on GHC 6.10.1 to Oleg. Hopefully an updated version will appear on hackage in the next few days. Yay! Thanks. I've been waiting. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type Family Relations
Excerpts from Thomas M. DuBuisson's message of Sat Jan 03 09:22:47 -0600 2009: Mandatory contrived example: type family AddressOf h type family HeaderOf a -- I'm looking for something to the effect of: type axiom HeaderOf (AddressOf x) ~ x -- Valid: type instance AddressOf IPv4Header = IPv4 type instance HeaderOf IPv4 = IPv4Header -- Invalid type instance AddressOf AppHeader = AppAddress type instance HeaderOf AppAddress = [AppHeader] So this is a universally enforced type equivalence. The stipulation could be arbitrarily complex, checked at compile time, and must hold for all instances of either type family. Am I making this too hard? Is there already a solution I'm missing? The problem is that type classes are open - anybody can extend this family i.e. type instance AddressOf IPv4Header = IPv4 type instance HeaderOf IPv4 = IPv4Header type instance AddressOf IPv6Header = IPv4 ipv4func :: (AddressOf x ~ IPv4) = x - ... And it will perfectly accept arguments with a type of IPv6Header. There is a proposal for extending GHC to support type invariants of this nature, but it is not implemented: http://tomschrijvers.blogspot.com/2008/11/type-invariants-for-haskell.html Austin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Weekly News: Issue 99 - January 3, 2009
--- Haskell Weekly News http://sequence.complete.org/hwn/20090103 Issue 99 - January 03, 2009 --- Welcome to issue 99 of HWN, a newsletter covering developments in the [1]Haskell community. Happy new year to all! May 2009 be a year full of joy, family, friends, professional success, much Haskell hacking, and a minimal number of rabid weasels. Just in case. Announcements #haskell IRC channel reaches 600 users. Don Stewart [2]announced that 7 years after its inception, under the guiding hand of Shae Erisson (aka shapr), the [3]#haskell IRC channel on freenode has reached 600 concurrent users! citeproc-hs-0.2. andrea rossato [4]announced the release of [5]citeproc-hs-0.2, a Haskell implementation of the Citation Style Language, which adds a Bibtex like citation and bibliographic formatting and generation facility to [6]pandoc. This version adds support for citation collapsing, a wrapper around [7]hs-bibutils, and some [8]API documentation. hs-bibutils-0.1. andrea rossato [9]announced the first release of [10]hs-bibutils, Haskell bindings to Chris Putnam's [11]bibutils. Bibutils is a library and a set of bibliographic utilities to interconvert between various bibliography database formats using a common MODS-format XML intermediate. Haskell koans. Gwern Branwen [12]issued an RFK (Request for [13]Koans), following the success of his CFH (Call for [14]Haiku). [ANN] Haskell web server + wiki: salvia-0.0.4 + orchid-0.0.6. Sebastiaan Visser [15]announced the release of three new packages: [16]salvia, a lightweight modular web server framework; [17]orchid, a(nother) wiki written in Haskell, using Darcs as a versioning back-end and Salvia as the application server; and [18]orchid-demo, a simple demo application using Salvia and Orchid to serve an example darcs repository. You can play around with an [19]online demo. gitit-0.4.1, recaptcha-0.1. John MacFarlane [20]announced the release of [21]gitit-0.4.1, a wiki program that stores pages in a git repository. This release adds support for (optional) captchas, using the reCAPTCHA service. The reCAPTCHA code has been packaged as a separate library on Hackage, [22]recaptcha. monte-carlo-0.2, gsl-random-0.2.3. Patrick Perry [23]announced the release of a new version of the [24]monte-carlo package. The new version includes a more general type class, MonadMC, which allows all the functions to work in both MC and MCT monads; functions to sample from discrete distributions, and functions to sample subsets. There is also a [25]quick tutorial. Reading group for Programming Collective Intelligence. Creighton Hogg [26]announced that he would like to start a small group for the O'Reilly book [27]Programming Collective Intelligence, to work through translating some of the examples to Haskell. Email Creighton if you are interested in participating. Maintaining laziness. Henning Thielemann [28]announced that he has written a [29]tutorial on how to make functions lazy and how to test whether they are actually lazy. Request for feedback: Understanding Haskell Monads. Ertugrul Soeylemez [30]requested feedback on a new [31]monad tutorial. Discussion How do we decide on the new logo?. Fritz Ruehr began a [32]discussion of how to go about choosing a winner of the [33]Great 2009 Haskell Logo Contest. Weigh in if you care! Jobs Two Positions as Associate Professor in Software Engineering at Chalmers University. Koen Claessen [34]announced the availability of [35]two positions as Associate Professor at Chalmers University in Gothenburg, Sweden, within the division of Software Engineering and Technology at the department of Computer Science and Engineering. The application deadline is January 12, 2009. Blog noise [36]Haskell news from the [37]blogosphere. * GHC / OpenSPARC Project: [38]Bootstrapping. * Dan Piponi (sigfpe): [39]Rewriting Monadic Expressions with Template Haskell. * GHC / OpenSPARC Project: [40]Fighting dependencies. * GHC / OpenSPARC Project: [41]A new year and a new project. * Alson Kemp: [42]2009: The Year Of Hackage. * Patrick Perry: [43]Monte Carlo Poker Odds. * Joachim Breitner: [44]Handling explicit and implicit recursion in Haskell data. * Luke Palmer: [45]Domain Convergence. * Eric Kow (kowey): [46]riot is almost a Haskell mail client. * John Goerzen (CosmicRay): [47]Real World Haskell update. * Alson Kemp: [48]A Plea For cabal install. * Alson Kemp: [49]Cyptol on Slashdot. Quotes of the Week * lilac: bohdan how do I see the number of reductions required to calculate something? lilac bohdan: the usual method is to ask Cale to reduce
Re: [Haskell-cafe] [ANN] Haskell web server + wiki: salvia-0.0.4 + orchid-0.0.6
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 On Thu, Jan 1, 2009 at 9:04 AM, Sebastiaan Visser wrote: Happy new year, you all! I'm pleased to announce three new packages on Hackage: I had some trouble getting all dependencies right on systems other than my own. Using `cabal install' seems to behave differently from `./Setup install' in the package directory, but this may vary from system to system. It is known to work at least on Macosx and Linux with GHC 6.8, 6.10 or even 6.11. Pdflatex is needed for PDF generation, dvipng for inline formulas. Have fun and best wishes for this new year! [1] http://funct.org/wiki/ [2] http://funct.org/wiki/data/Index.html [3] http://www.cs.uu.nl/wiki/HUT/AttributeGrammarSystem Sebastiaan: are there any public repos for these packages? - -- gwern -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREKAAYFAklfryAACgkQvpDo5Pfl1oJuIACdHtzspXuAt3Bp4UXAubvT0UvD RtkAn1PlqWYbAxLRG4WOqAmZw6Dd6f/1 =wwLT -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Use of abbreviations in Haskell
Isaac Dupree m...@isaac.cedarswampstudios.org writes: Derek Elkins wrote: I haven't been able to find any semantic difficulties with this addition. I like it too... what I run into is that there's an implicit assumption that module of name Foo.Bar.Baz *must* be found in a file Foo/Bar/Baz.[l]hs . Ah, surely mere practicalities will not stand in the way of improving the usability of the language? GHC uses this all the time ..unless you want a compiler, I guess. How about this: A module may be defined in a file with a name corresponding to the module name, or any dot-separated prefix of it? I.e. the file Foo/Bar.hs will define module Foo.Bar and optionally Foo.Bar.Baz as well? GHC should then be able to find it, and I believe it already has a prioritized search mechanism (presumably, the file could be named Foo.Bar.hs, too). -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: How do we decide on the new logo?
On 3 jan 2009, at 17:33, Sebastian Sylvan wrote: On Sat, Jan 3, 2009 at 3:15 AM, rocon...@theorem.ca wrote: On Sat, 3 Jan 2009, Achim Schneider wrote: Step 2: Determine the winner by polling preferences, same-level preference (ambivalence) allowed (eg. place 1 for logos C and D, place 2 for A and place 3 for B) The only reasonable method of voting using this ranking data is one of the Condorcet methods. How you break ties doesnt matter much to me. Wikimedia, Debian, Gentoo, and Software in the Public Intrest all use Schulze method for what that is worth. Yes. Condorcet voting picks the best compromise and is IMO the way to do this - we won't all agree on the best logo, but at least we can pick the least disliked one. It doesn't need to be super sophisticated, just a box next to each logo where you can enter a rank in any range you like (1 being most preferred, empty boxing being equivalent to +Inf), allowing multiple entries to share the same rank. Since there already is a condorcet voting package on Hackage, I made a simple (HAppS powered) web app where you can drag-n-drop your preferences. See http://github.com/eelco/voting/tree/master for the code (contributions more than welcome! Note, there's also a jQuery branch which has a bit different drag-n-drop behaviour) and http://code.tupil.com/voting/ for a live demo. It needs a bit more work but mainly a whole bulk of decisions, like * Limit voting, if so how? Email confirmation, IP based, vote once, once per day? * Maybe don't show the results until the contest is over? I, for one, very much welcome any benevolent dictator to make these decisions, because we can probably argue about pros and cons for months. Since Don started the contest (http://www.haskell.org/pipermail/haskell-cafe/2008-December/051836.html ) and also seems to have some ideas about the voting process (http://www.haskell.org/pipermail/haskell-cafe/2008-December/052257.html ), I hereby officially appoint him to lead to masses. (Does it work like that? ;) -- Regards, Eelco Lempsink PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Pattern combinators
David Menendez dave at zednenem.com writes:
On Sun, Dec 21, 2008 at 10:14 PM, Andrew Wagner
wagner.andrew at gmail.com wrote:
I'd love to see a copy of this go up on hackage for experimentation.
Would
you care to upload your code, or send it to me so I can upload it?
I've uploaded my latest version to http://hpaste.org/13263. It
explicitly makes patterns polymorphic over the answer type of the case
statement by making Pattern a newtype and universally quantifying the
(un)currying and matching functions.
For example,
(-) :: Pattern a () vec - Curry vec ans - Case a ans
I'm not sure it makes sense to create a package just yet. At the very
least, you should ask Morten Rhiger first. The type signatures are
mine, but the code is mostly straight transcriptions from his paper.
Hi,
I've tried to undestand the paper, in particular the relation between
the combinators written in cps style and combinators written using a
Maybe type (i.e pattern matching functions returning Maybe to signal
success or failure). The code below gives an implementation of the
basic pattern matching functions on top of two possible implementation
of an abstract interface for building and using bindings. In particular
using type families it seems to be possible to automatically construct a
function inj to convert between a function in the form a-b-c-d to a
function in the form (a,(b,c,())) - d, thereby removing the need of
building such coverter via the pattern matching functions like suggested
in the paper.
Since I'm an Haskell begineer I would appreciate very much comments or
suggestions for improvements.
Best,
Massimiliano Gubinelli
Here the code:
---
{-# LANGUAGE TypeFamilies, MultiParamTypeClasses,
FlexibleInstances, RankNTypes #-}
module PM where
-- inj converts a function of the form a - b - c - d to the
-- uniform representation (a,(b,(c,( - d
class Fn a c where
type Fnq a c
inj :: Fnq a c - a - c
instance Fn () c where
type Fnq () c = c
inj f () = f
instance Fn b c = Fn (a,b) c where
type Fnq (a,b) c = a - Fnq b c
inj f (a,b) = inj (f a) b
-- pattern matching, cps style
-- a binding function has three inputs: ks kf v. v is a list of
-- current bindings.
newtype PatA a b = PatA {
unPatA :: forall ans. (b - ans) - ans - a - ans
}
applyA :: PatA a b - (b - c) - c - a - c
applyA (PatA p) ks kf v = p ks kf v
meetA :: PatA a b - PatA b c - PatA a c
meetA (PatA a) (PatA b) = PatA $ \ ks kf - a (b ks kf) kf
joinA :: PatA a b - PatA a b - PatA a b
joinA (PatA a) (PatA b) = PatA $ \ ks kf v - a ks (b ks kf v) v
anyA :: PatA a a
anyA = PatA $ \ ks kf - ks
noneA :: PatA a a
noneA = PatA $ \ ks kf v - kf
varA :: x - PatA a (x,a)
varA x = PatA $ \ ks kf v - ks (x,v)
pairA a b (x,y) = meetA (a x) (b y)
conA a x = if a == x then anyA else noneA
andA a b x = meetA (a x) (b x)
orA p n x = joinA (p x) (n x)
matchA val pat = pat val ()
caseA a fa fb x v = applyA (a x) (inj fa) (fb x v) v
otherwiseA kf = \x v - kf
isA p x = matchA x $ caseA p (\_ - True) $ otherwiseA False
testA1 z = matchA z $ caseA (conA (1,2)) (first match) $
caseA (pairA (conA 1) varA)
(\x - second match ++ show x) $
caseA (pairA varA varA)
(\x y - third match ++ show x) $
otherwiseA mismatch
-- pattern matching, Maybe style
-- a binding function receives a list of current bindings and returns
-- a Maybe type containing the list of updated bindings in case of
-- success
newtype PatB a b = PatB { unPatB :: a - Maybe b }
applyB :: PatB a b - (b - c) - c - a - c
applyB (PatB p) ks kf v = maybe kf ks (p v)
meetB :: PatB a b - PatB c a - PatB c b
meetB (PatB a) (PatB b) = PatB $ \v - (b v) = a
joinB :: PatB a b - PatB a b - PatB a b
joinB (PatB a) (PatB b) = PatB $ \v - maybe (b v) Just (a v)
anyB :: PatB a a
anyB = PatB $ \v - Just v
noneB :: PatB a a
noneB = PatB $ \v - Nothing
varB :: x - PatB a (x,a)
varB x = PatB $ \v - Just (x,v)
pairB a b (x,y) = meetB (a x) (b y)
conB a x = if a == x then anyB else noneB
orB a b x = joinB (a x) (b x)
andB a b x = meetB (a x) (b x)
matchB val pat = pat val ()
--caseB a fa fb x v = maybe (fb x v) (inj fa) ((unPatB $ a x) v)
caseB a fa fb x v = applyB (a x) (inj fa) (fb x v) v
otherwiseB f = \x v - f
isB p x = matchB x $ caseB p (\_ - True) $ otherwiseB False
testB1 z = matchB z $ caseB (pairB (conB 1) (conB 2)) (first match) $
caseB (pairB (conB 1) varB) (\x - second match ++ show x) $
caseB (pairB varB varB) (\x y - third match ++ show x) $
otherwiseB mismatch
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] #haskell IRC channel reaches 600 users
On Fri, 02 Jan 2009 21:27:24 +0100, Don Stewart d...@galois.com wrote: A small announcement :) 7 years after its inception, under the guiding hand of Shae Erisson (aka shapr), the #haskell IRC channel[1] on freenode has reached 600 concurrent users! It's now in the top 3 language channels by size. Some more statistics can be found at http://www.langpop.com/ An interesting quote from this site: It's interesting to note how languages like Haskell and Erlang are talked about a lot, despite scoring fairly low on the normalized popularity chart above. People are interested in them, but haven't begun to use them on a large scale yet. We have to create more webpages about Haskell (containing the words programming and Haskell) to score better! :) And there should be more Haskell jobs :) Other sites with statistics: http://www.tiobe.com/content/paperinfo/tpci/index.html http://www.complang.tuwien.ac.at/anton/comp.lang-statistics/ An article about what makes a language popular: http://www.paulgraham.com/popular.html -- Regards, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type Family Relations
I've been fighting this same problem for a while. The solution I've come up with is to encode the axioms into a typeclass which gives you a proof of the axioms. Here's an excerpt from some code I've been playing around with; HaskTy and Lift are type families. -- Theorem: for all t instance of Lift, (forall env. HaskTy (Lift t) env == t) data HaskTy_Lift_Id t env = (t ~ HaskTy (Lift t) env) = HaskTy_Lift_Id class Thm_HaskTy_Lift_Id t where thm_haskty_lift_id :: forall env. HaskTy_Lift_Id t env instance Thm_HaskTy_Lift_Id Int where thm_haskty_lift_id = HaskTy_Lift_Id instance Thm_HaskTy_Lift_Id Bool where thm_haskty_lift_id = HaskTy_Lift_Id lemma_haskty_lift_id_app :: HaskTy_Lift_Id a env - HaskTy_Lift_Id b env - HaskTy_Lift_Id (a - b) env lemma_haskty_lift_id_app HaskTy_Lift_Id HaskTy_Lift_Id = HaskTy_Lift_Id instance (Thm_HaskTy_Lift_Id a, Thm_HaskTy_Lift_Id b) = Thm_HaskTy_Lift_Id (a - b) where thm_haskty_lift_id = lemma_haskty_lift_id_app thm_haskty_lift_id thm_haskty_lift_id As you can see, I encode a witness of the type equality into a concrete data type. You then direct the typechecker as to how to prove the type equality using the typeclass mechanism; the class instances closely mirror the type family instances. You then add this typeclass as a context on functions that require the equality. Control.Coroutine[1] uses a similar restriction: class Connect s where connect :: (s ~ Dual c, c ~ Dual s) = InSession s a - InSession c b - (a,b) A cleaner solution, that sadly doesn't work in GHC6.10 [2], would be something like: class (s ~ Dual (Dual s)) = Connect s where connect :: InSession s a - InSession (Dual s) b - (a,b) The difference is mainly one of efficiency; even though there is only one constructor for Thm_HaskTy_Lift_Id t env, at runtime the code still has to prove that evaluation terminates (to avoid _|_ giving an unsound proof of type equality). This means that deeply nested instances of the (a - b) instance require calling dictionary constructors to match the tree, until eventually we see that each leaf is a valid constructor. If the type equality could be brought into scope by just bringing the typeclass into scope, the dictionaries themselves could remain unevaluated at runtime. -- ryan [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Coroutine [2] http://hackage.haskell.org/trac/ghc/ticket/2102 On Sat, Jan 3, 2009 at 7:22 AM, Thomas DuBuisson thomas.dubuis...@gmail.com wrote: Cafe, I am wondering if there is a way to enforce compile time checking of an axiom relating two separate type families. Mandatory contrived example: type family AddressOf h type family HeaderOf a -- I'm looking for something to the effect of: type axiom HeaderOf (AddressOf x) ~ x -- Valid: type instance AddressOf IPv4Header = IPv4 type instance HeaderOf IPv4 = IPv4Header -- Invalid type instance AddressOf AppHeader = AppAddress type instance HeaderOf AppAddress = [AppHeader] So this is a universally enforced type equivalence. The stipulation could be arbitrarily complex, checked at compile time, and must hold for all instances of either type family. Am I making this too hard? Is there already a solution I'm missing? Cheers, Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type Family Relations
Hello,
Usually, you can program such things by using super-classes. Here is
how you could encode your example:
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
FlexibleInstances #-}
class HeaderOf addr hdr | addr - hdr
class HeaderOf addr hdr = AddressOf hdr addr | addr - hdr
data IPv4Header = C1
data IPv4 = C2
data AppAddress = C3
data AppHeader = C4
instance AddressOf IPv4Header IPv4
instance HeaderOf IPv4 IPv4Header
{- results in error:
instance AddressOf AppHeader AppAddress
instance HeaderOf AppAddress [AppHeader]
-}
Hope that this helps,
Iavor
On Sat, Jan 3, 2009 at 7:22 AM, Thomas DuBuisson
thomas.dubuis...@gmail.com wrote:
Cafe,
I am wondering if there is a way to enforce compile time checking of
an axiom relating two separate type families.
Mandatory contrived example:
type family AddressOf h
type family HeaderOf a
-- I'm looking for something to the effect of:
type axiom HeaderOf (AddressOf x) ~ x
-- Valid:
type instance AddressOf IPv4Header = IPv4
type instance HeaderOf IPv4 = IPv4Header
-- Invalid
type instance AddressOf AppHeader = AppAddress
type instance HeaderOf AppAddress = [AppHeader]
So this is a universally enforced type equivalence. The stipulation
could be arbitrarily complex, checked at compile time, and must hold
for all instances of either type family.
Am I making this too hard? Is there already a solution I'm missing?
Cheers,
Tom
___
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] teaching functional programming at work
I am seeking suggestions from the haskell cafe for teaching functional programming concepts to colleagues at work. I'm currently working on a project using ocaml and functional programming techniques, and am a lone ranger at my workplace when it comes to this sort of thing (we are primarily a python shop). However there seems to be a growing curiosity in functional programming, and I think there's a lot to be learned from from it whether one chooses a functional language for their next big project or not. But I'm a practitioner, not an academic or lecturer, and although I find the idea of helping my colleagues understand these concepts to be an exciting prospect, I'm not really sure where to start in terms of materials or overall direction. My sense is to form a study group (perhaps going through Real World Haskell together), but I'm a little afraid of assembling people together for a now what? experience. So my first question is whether this is even a good idea? Some things I think would be useful to get across are: - fp is more than just an exercise in avoiding assignment statements -- why a smart programmer should care? - reading knowledge of ocaml and/or haskell (even syntax, precedence and infix operators can be an initial stumbling block) - core concepts: type classes, proper tail recursion, higher-order functions, folds, combinators, monads, monad transformers, arrows - evidence that concise expression can lead to less bugs / better maintainability (hard to prove, but perhaps a sense can be conveyed) - relationship between types / theorems / programs / proofs and why this is important for the future of software Regarding this last point, my own sense has been that by leveraging a powerful type system such as found in ocaml or haskell has allowed me to achieve things I never would have been able to without it (or at least would have ended up with a much less elegant implementation and much more debugging) but many seem to find types to be either an impedance to getting things done quickly, or at best irrelevant. I know this is for the most part a religious war, but I would like my colleagues to arrive at their opinion from an informed perspective, which means learning that there's more to typeful programming than what is presented by java or c++. Finally, any comments on how to make the learning experience fun, engaging, and a positive experience would be greatly appreciated. Warren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to check object's identity?
2009/1/3 Xie Hanjian jan.h@gmail.com Hi, I tried this in ghci: Prelude 1:2:[] == 1:2:[] True Does this mean (:) return the same object on same input, Also, in functional programming, *every* function returns the same output for the same input. That's part of the definition of function. :-) Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Use of abbreviations in Haskell
Ketil Malde wrote: A module may be defined in a file with a name corresponding to the module name, or any dot-separated prefix of it? I.e. the file Foo/Bar.hs will define module Foo.Bar and optionally Foo.Bar.Baz as well? GHC should then be able to find it, and I believe it already has a prioritized search mechanism (presumably, the file could be named Foo.Bar.hs, too). I don't think GHC actually allows that (Foo.Bar.hs, ever). But your suggestion could work. 1. Try Foo/Bar/Baz.hs ; if it exists, end search (and error if it does not contain Foo.Bar.Baz, obviously as the file's top-level module). 2. Try Foo.Bar.hs ; if it exists, end search (and error if it does not contain Foo.Bar.Baz, obviously as a sub-module). 3. Try Foo.hs ; if it exists, end search (and error if it does not contain Foo.Bar.Baz, obviously as a sub-module... or possibly as a sub-sub-module?). 4. give up :-) Note though, that local modules tempt us to a couple other things too, even though they're not necessary to the proposal and would complicate it: - access-controlled modules (e.g. if other code can't import Foo.Bar.Baz) - relative-path imports / module names (e.g. if in Foo/Bar.hs we make Baz and try to import it some way with import Baz) and as we already mentioned, it would likely involve some implicit importing of the sub-module. translating into ordinary haskell: I think my module-search mechanism makes a well-defined, deterministic way to find the right module, no complex translation necessary (except layout rule madness maybe?). Implicit importing: submodule syntax implies adding an import The.Module.Name line at that point in the containing file. This would suggest that submodules must be at the top, among the imports, because all imports must syntactically be at the beginning of the file -- and there's a reason for this. Bother! Even if the reason is dependency chasing, one would think same-file dependencies aren't important, but the submodules themselves can import things from other files, so those lines should need to be near the beginning anyway. so an example could be module MyData ( module MyData.Sub, -- or equivalently, D(..) transform ) where module MyData.Sub --or module Sub ?? that seems a bit too ad-hoc though where data D = E | F transform :: D - D transform F = E transform E = F ~Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: bytestring-trie 0.1.1 (bugfix)
-- bytestring-trie 0.1.1 (bugfix) An efficient finite map from (byte)strings to values. The implementation is based on big-endian patricia trees, like Data.IntMap. We first trie on the Word8 elements of a Data.ByteString, sharing string prefixes where possible, and then trie on the big-endian bit representation of those elements. Patricia trees have efficient algorithms for union and other merging operations, but they're also quick for lookups and insertions. -- Changes * Fixed a bug in lookupBy_ pointed out by Maxime Henrion. The bug affects all lookup-like functions when a prefix of the query matches only part of a shared prefix in the trie (e.g. looking for fi in a trie containing [foo,bar,baz], but not when looking up fo, food, or bag). * By popular demand Trie now has a Binary instance. This adds a new dependency on the binary package. The dependency shouldn't be onerous to anyone, but let me know if it is. -- Links Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring-trie Darcs: http://code.haskell.org/~wren/bytestring-trie/ Haddock (Darcs version): http://code.haskell.org/~wren/bytestring-trie/dist/doc/html/bytestring-trie/ -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to check object's identity?
* Luke Palmer lrpal...@gmail.com [2009-01-03 18:46:50 -0700]:
2009/1/3 Xie Hanjian jan.h@gmail.com
Hi,
I tried this in ghci:
Prelude 1:2:[] == 1:2:[]
True
Does this mean (:) return the same object on same input,
Also, in functional programming, *every* function returns the same output
for the same input. That's part of the definition of function. :-)
This is true in Haskell, but may not true in Scheme (I guess also false
in Lisp).
In DrScheme:
(eq? (cons 1 2) (cons 1 2))
#f
(equal? (cons 1 2) (cons 1 2))
#t
Although equal? treats the two as the *same*, they're different lists
because if we modify one (e.g by set-car!) the other won't be affected.
So here comes another question: when we say a function always give the
same output for the same input, what the *same* means here? ídentity
or equality?
Thanks
Jan
Luke
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
jan=callcc{|jan|jan};jan.call(jan)
pgpBNyEg1SLvQ.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Use of abbreviations in Haskell
Cafe,
I was going to write about this earlier, but I'm so ill read on the
record selector papers that I deleted the draft.
My proposal would be for each selector name to be a special type of
phantom type class (existing in the intermediate language only).
This type class would not be accessible by the programmer and thus
s/he couldn't make a polymorphic function for which specialization
would be needed. In other words - in normal circumstances there is
no need for dictionaries and thus no run-time difference between this
method and using different record names.
Example:
data IPv4Hdr = Hdr4 { src, dst :: IPv4 }
data IPv6Hdr = Hdr6 { src, dst :: IPv6 }
func4 :: IPv4Hdr - IO ()
func4 hdr = do
let s = src hdr
...
func6 :: IPv6Hdr - IO ()
func6 hdr = do
let s = src hdr
...
At some intermediate stage you'd see:
class Src h s where
src :: h - s
class Dst h d where
dst :: h - d
instance Src IPv4Hdr IPv4 where
src (IPv4 s _) = s
instance Dst IPv4Hdr IPv4 where
dst (IPv4 _ d) = d
-- repeat for IPv6
The only point of frustration I see is if the programmer manually
makes both data types an instance of a programmer-visible type class,
thus making a polymorphic function.
class IPHdr a
instance IPHdr IPv4Hdr
instance IPHdr IPv6Hdr
sendPing :: (IPHdr a) = a - IO ()
sendPing p = networkSend (dst p) pingPayload
In this case I'd vote for specializing the function so there still
aren't any extra dictionaries, but I know that is not always optimal.
Tom
On Sat, Jan 3, 2009 at 10:08 PM, Isaac Dupree
m...@isaac.cedarswampstudios.org wrote:
Ketil Malde wrote:
A module may be defined in a file with a name corresponding to the
module name, or any dot-separated prefix of it? I.e. the file
Foo/Bar.hs will define module Foo.Bar and optionally Foo.Bar.Baz as
well?
GHC should then be able to find it, and I believe it already has a
prioritized search mechanism (presumably, the file could be named
Foo.Bar.hs, too).
I don't think GHC actually allows that (Foo.Bar.hs, ever). But your suggestion
could work.
1. Try Foo/Bar/Baz.hs ; if it exists, end search (and error if it does not
contain Foo.Bar.Baz, obviously as the file's top-level module).
2. Try Foo.Bar.hs ; if it exists, end search (and error if it does not contain
Foo.Bar.Baz, obviously as a sub-module).
3. Try Foo.hs ; if it exists, end search (and error if it does not contain
Foo.Bar.Baz, obviously as a sub-module... or possibly as a sub-sub-module?).
4. give up :-)
Note though, that local modules tempt us to a couple other things too, even
though they're not necessary to the proposal and would complicate it:
- access-controlled modules (e.g. if other code can't import Foo.Bar.Baz)
- relative-path imports / module names (e.g. if in Foo/Bar.hs we make Baz and
try to import it some way with import Baz)
and as we already mentioned, it would likely involve some implicit importing
of the sub-module.
translating into ordinary haskell:
I think my module-search mechanism makes a well-defined, deterministic way to
find the right module, no complex translation necessary (except layout rule
madness maybe?).
Implicit importing: submodule syntax implies adding an import
The.Module.Name line at that point in the containing file. This would
suggest
that submodules must be at the top, among the imports, because all imports
must syntactically be at the beginning of the file -- and there's a reason for
this. Bother! Even if the reason is dependency chasing, one would think
same-file dependencies aren't important, but the submodules themselves can
import things from other files, so those lines should need to be near the
beginning anyway.
so an example could be
module MyData
(
module MyData.Sub, -- or equivalently, D(..)
transform
)
where
module MyData.Sub --or module Sub ?? that seems a bit too ad-hoc though
where
data D = E | F
transform :: D - D
transform F = E
transform E = F
~Isaac
___
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] How to check object's identity?
2009/1/3 Xie Hanjian jan.h@gmail.com
* Luke Palmer lrpal...@gmail.com [2009-01-03 18:46:50 -0700]:
2009/1/3 Xie Hanjian jan.h@gmail.com
Hi,
I tried this in ghci:
Prelude 1:2:[] == 1:2:[]
True
Does this mean (:) return the same object on same input,
Also, in functional programming, *every* function returns the same output
for the same input. That's part of the definition of function. :-)
This is true in Haskell, but may not true in Scheme (I guess also false
in Lisp).
I, like many arrogant Haskellers, reject Scheme and other such impure
languages as functional. At least until I turn on my brain.
So, revise the beginning of my statement to Also, in *pure* functional
programming, ...
Luke
In DrScheme:
(eq? (cons 1 2) (cons 1 2))
#f
(equal? (cons 1 2) (cons 1 2))
#t
Although equal? treats the two as the *same*, they're different lists
because if we modify one (e.g by set-car!) the other won't be affected.
So here comes another question: when we say a function always give the
same output for the same input, what the *same* means here? ídentity
or equality?
Thanks
Jan
Luke
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
jan=callcc{|jan|jan};jan.call(jan)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type Family Relations
Thank you all for the responses. I find the solution that omits type
families [Diatchki] to be too limiting while the solution 'class (Dual
(Dual s) ~ s) =' [Ingram] isn't globally enforced. I've yet to
closely study your first solution, Ryan, but it appears to be what I
was looking for - I'll give it a try in the coming week.
Tom
On Sat, Jan 3, 2009 at 8:18 PM, Iavor Diatchki iavor.diatc...@gmail.com wrote:
Hello,
Usually, you can program such things by using super-classes. Here is
how you could encode your example:
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
FlexibleInstances #-}
class HeaderOf addr hdr | addr - hdr
class HeaderOf addr hdr = AddressOf hdr addr | addr - hdr
data IPv4Header = C1
data IPv4 = C2
data AppAddress = C3
data AppHeader = C4
instance AddressOf IPv4Header IPv4
instance HeaderOf IPv4 IPv4Header
{- results in error:
instance AddressOf AppHeader AppAddress
instance HeaderOf AppAddress [AppHeader]
-}
Hope that this helps,
Iavor
On Sat, Jan 3, 2009 at 7:22 AM, Thomas DuBuisson
thomas.dubuis...@gmail.com wrote:
Cafe,
I am wondering if there is a way to enforce compile time checking of
an axiom relating two separate type families.
Mandatory contrived example:
type family AddressOf h
type family HeaderOf a
-- I'm looking for something to the effect of:
type axiom HeaderOf (AddressOf x) ~ x
-- Valid:
type instance AddressOf IPv4Header = IPv4
type instance HeaderOf IPv4 = IPv4Header
-- Invalid
type instance AddressOf AppHeader = AppAddress
type instance HeaderOf AppAddress = [AppHeader]
So this is a universally enforced type equivalence. The stipulation
could be arbitrarily complex, checked at compile time, and must hold
for all instances of either type family.
Am I making this too hard? Is there already a solution I'm missing?
Cheers,
Tom
___
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] Updating doubly linked lists
G'Day,
and phew... quite a lot of code to grok. Thanks for the answers, they're much
appreciated.
On Sun, Jan 4, 2009 at 1:43 AM, Niklas Broberg niklas.brob...@gmail.com wrote:
What you need is for the nodes to keep track of the length of the
list. Here's a different solution from that oleg posted, to me it's
slightly more intuitive, since the updates work directly on the dlists
instead of via (elegant) proxy functions.
I had exactly the same thoughts after I realized that, if one wants to
update only
the non cyclic part of the list one has to know where the non cyclic
part ends. But
the only way to know that, is by keeping track of the length of the
list and using
this to find out when to tie the knot. So your solution is also more
intuitive to
me but if I'm not mistaken it has update complexity linear in the number of
elements in the list whereas Oleg's solution is logarithmic.
mkRestDList :: Int - [a] - DList a - DList a - (DList a, DList a)
mkRestDList _ [] _ farRight =
(farRight, farRight) -- will only happen if the initial list is singleton
mkRestDList len [x] nearLeft farRight =
let this = DNode len nearLeft x farRight
in (this, this)
mkRestDList len (x:xs) nearLeft farRight =
let this = DNode len nearLeft x nearRight
(nearRight,farLeft) = mkRestDList len xs this farRight
in (this,farLeft)
updateRestD :: Int - DList a - DList a - DList a - (DList a, DList a)
updateRestD 0 _ _ farRight =
(farRight, farRight) -- will only happen if the initial list is singleton
updateRestD 1 (DNode len _ x _) nearLeft farRight =
let this = DNode len nearLeft x farRight in (this, this)
updateRestD n (DNode len _ x r) nearLeft farRight =
let this = DNode len nearLeft x nearRight
(nearRight,farLeft) = updateRestD (n-1) r this farRight
in (this,farLeft)
updateRestD _ Empty _ _ = undefined -- can't happen
I think you can drop the second case in those two functions if you rewrite the
first case like this:
mkRestDList _ [] nearLeft farRight = (farRight, nearLeft)
resp.
updateRestD 0 _ nearLeft farRight = (farRight, nearLeft)
On Sat, Jan 3, 2009 at 8:51 PM, o...@okmij.org wrote:
Stephan Guenther wrote:
The algorithm is essentially imperative (and so permits identity
checking and in-place `updates') but implemented purely
functionally. No destructive updates are ever used. Therefore, all the
changes can be undone and re-done, and the code is MT-safe. The code
is easily generalizable to 2D.
Thanks for your answer. As I'll explain below I also thought about
using a Map for
the 2D case, but wouldn't have thought of it in the one dimensional case as my
intuition would have been to use Niklas' solution there. Thanks for putting my
thoughts in a different direction.
Yet the thing that really puzzled me in the list case was, that I was
searching for
a solution without using auxiliary data like the length or delegating
the update to a
data structure which already supported it. I'm pretty sure by now that its
impossible without using zippers or something else.
It is not for nothing Haskell is called the best imperative
language. One can implement imperative algorithms just as they are --
purely functionally, without any monads or other categorical notions.
Amen to that.
-- The insert operation below makes a cyclic list
-- The other operations don't care
-- Insert to the right of the current element, if any
-- Return the DL where the inserted node is the current one
insert_right :: a - DList a - DList a
insert_right x dl | is_empty dl =
let ref = dl_counter dl
-- the following makes the list cyclic
node = Node{node_val = x, node_left = ref, node_right = ref}
in DList{dl_counter = succ ref,
dl_current = ref,
dl_mem = IM.insert ref node (dl_mem dl)}
insert_right x d...@dlist{dl_counter = ref, dl_current = curr, dl_mem = mem} =
DList{dl_counter = succ ref, dl_current = ref,
dl_mem = IM.insert ref new_node $ IM.insert curr curr_node' mem}
where
curr_node = get_curr_node dl
curr_node'= curr_node{node_right = ref}
new_node = Node{node_val = x, node_left = curr,
node_right = node_right curr_node}
Could it be that there's a small inconsistency in the fact that if you
don't update the
left_node ref of curr_node? This is nearly never a problem except when you do
insert_right on a DList with only one element. In that case node_left
of curr_node
references itself and should be updated to reference it's new right
(and therefore
also left wraparound) neighbour. If I'm right this leads to the fact
that DList is only
right cyclic while the left end always wraps around to itself.
I know that this is easily corrected (if wanted), I just want to know if I'm
understanding the code correctly.
On Sat, Jan 3, 2009 at 10:37 PM, Apfelmus, Heinrich
apfel...@quantentunnel.de wrote:
Ah, so you have a rectangular (or later hexagonal?) 2D grid? I suggest
representing it as
Re: [Haskell-cafe] How to check object's identity?
Luke Palmer wrote: I, like many arrogant Haskellers, reject Scheme and other such impure languages as functional. At least until I turn on my brain. If Haskell is functional, then so is Scheme - it's just that Scheme lets you use IORefs and the IO monad without going to nearly as much trouble. Anton ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
