headers
Fergus Henderson | 1 Sep 2005 02:09
Favicon

Re: embedding prolog in haskell.

On 18-Aug-2005, Keean Schupke <k.schupke <at> imperial.ac.uk> wrote:
> I was wondering if anyone has any comments on my 
> implementation of unify? For example can the algorithm be simplified 
> from my nieve attempt? Most importantly is it correct?
> 
>    type Subst = [(Vname,Term)]
>    data Term = Func Fname [Term] | Var Vname deriving (Eq,Show)
>    type Fname = String
>    data Vname = Name String | Auto Integer deriving (Eq,Show)
> 
>    unify :: Subst -> (Term,Term) -> [Subst]
>    unify s (t,u) | t == u = [s]

You should delete the line above.  It's not needed and could cause serious
efficiency problems.  With that line present, unifying two lists
of length N which differ only in the last element would take time
proportional to N squared, but without it, the time should be linear in N.

>    unify s (Var x,t) = [(x,t):s] -- no occurs check
>    unify s (t,Var x) = [(x,t):s] -- no occurs check

These are not right; you need to look up the variable x
in the substitution s, and if it is already bound, then
you need to unify what it is bound to with the term t.

--

-- 
Fergus J. Henderson                 |  "I have always known that the pursuit
Galois Connections, Inc.            |  of excellence is a lethal habit"
Phone: +1 503 626 6616              |     -- the last words of T. S. Garp.
(Continue reading)

Permalink | Reply | 1 comment |
headers
Juan Carlos Arevalo Baeza | 1 Sep 2005 09:41

Re: Monadic vs "pure" style (was: pros and cons of sta tic typing and side effects)

Philippa Cowderoy wrote:

> On Wed, 31 Aug 2005, Philippa Cowderoy wrote:
>
>> On Wed, 31 Aug 2005, Ben Lippmeier wrote:
>>
>>> I imagine this would be an absolute pain for library writers. Notice 
>>> that we get Data.Map.map but no Data.Map.mapM - or perhaps there's 
>>> some magical lifting combinator that I am not aware of?
>>
>>
>> sequence (Data.Map.map (\x -> someAction x) someMap)
>
>
> Or not - I really should've at least typechecked that before sending. 
> Wonder how fast toList and fromList are?

   "foldWithKey <#v%3AfoldWithKey> :: (k -> a -> b -> b) -> b -> Map 
<Data.Map.html#t%3AMap> k a -> b" looks promising... Lemme try my hand 
at it...

myMapM someAction someMap = Map.foldWithKey foldFunc (return Map.empty) 
someMap
    where
    foldFunc k a b = do
        m <- b
        c <- someAction a
        return (Map.insert k c m)

   Definitely typechecks and works, and it is O(n) but, alas, it runs
(Continue reading)

Permalink | Reply | 1 comment |
headers
Juan Carlos Arevalo Baeza | 1 Sep 2005 10:03

Re: Monadic vs "pure" style (was: pros and cons of sta tic typing and side effects)

Ben Lippmeier wrote:

>> to monads. If the idea is most clearly expressed
>> as a monad, use a monad. If the idea is most
>> clearly expressed recursively, write it recursively
>> (but perhaps wrap it in "return").
>
> There is no inherent advantage or disadvantage
>
> Perhaps the "inherent disadvantage" is that functions written in the 
> monadic style must have different types compared with their 
> conceptually similar non-monadic functions..
>
> mapM    :: Monad m => (a -> m b) -> [a] -> m [b]
> map     :: (a -> b) -> [a] -> [b]
>
> filter  :: (a -> Bool) -> [a] -> [a]
> filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
>
> foldl   :: (a -> b -> a) -> a -> [b] -> a
> foldM   :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
>
> Some would say "but they're different functions!", others would say 
> "close enough".

   Heh... I recently was experimenting with this separation... Check 
this out. If the Num class had been defined without having "Eq" as a 
prerequisite, you could do something like this:

---8<---------------------------------
(Continue reading)

Permalink | Reply | 751 comments |
headers
Yitzchak Gale | 1 Sep 2005 12:28

Re: Monadic vs "pure" style (was: pros and cons of sta tic typing and side effects)

On Thu, Sep 01, 2005 at 12:41:06AM -0700, Juan Carlos Arevalo Baeza wrote:
>   You can get the correct order by using lists, but you want to use the 
> "Asc" versions:
> 
> myMapM someAction someMap = do
>    list <- sequence $
>            map (\(k, a) -> someAction a >>= (\b -> return (k,b))) $
>            Map.toAscList someMap
>    return (Map.fromAscList list)
> 
> Should also be O(n).

I like this approach. You want to use
fromDistinctAscList though.

By analogy with the Prelude, I would make it
slightly more flexible as follows:

mySequence :: Monad m => Map.Map k (m a) -> m (Map.Map k a)
mySequence someMap = do
    list <- sequence $ map liftTuple $ Map.toAscList someMap
    return $ Map.fromDistinctAscList list
  where
    liftTuple (x, y) = do
      z <- y
      return (x, z)

myMapM :: Monad m => (a -> m b) -> Map.Map k a -> m (Map.Map k b)
myMapM f = mySequence . Map.map f
(Continue reading)

Permalink | Reply | 0 comments |
headers
Keean Schupke | 1 Sep 2005 16:17
Picon

Re: embedding prolog in haskell.

Thanks for that, altough I have completely rewritten it! Here's the new 
implementation:

    unify :: Subst -> (Term,Term) -> [Subst]
    unify sigma (s,t) = let
            s' = if isVar s then subst s sigma else s
            t' = if isVar t then subst t sigma else t
            in if isVar s' && s'==t' then [sigma] else if isFunc s' && 
isFunc t'
                    then if fname s' == fname t' && arity s' == arity t'
                            then unify' sigma (terms s') (terms t')
                            else []
                    else if not (isVar s)
                            then unify sigma (t',s')
                            else [s' ~> t' : sigma]

    unify' :: Subst -> [Term] -> [Term] -> [Subst]
    unify' s (t0:ts) (u0:us) = case unify s (t0,u0) of
            s <at> (_:_) -> unify' (concat s) ts us
            _ -> []
    unify' s [] [] = [s]
    unify' _ _ _ = []

Once again, thoughts or improvements greatly appreciated...

    Regards,
    Keean.

Fergus Henderson wrote:
(Continue reading)

Permalink | Reply | 0 comments |
headers
Keean Schupke | 1 Sep 2005 16:34
Picon

Re: pros and cons of static typing and side effects ?

Martin Vlk wrote:

>On pondělí 29 srpna 2005 8:57, Ketil Malde wrote:
>  
>
>>>It contains descriptions of lots of real-world problems and how
>>>      
>>>
>>They are only implementing TRUTH and CWB, no?
>>    
>>
>
>Yes, and lots of real-world situations that they faced during the development. 
>That's what I meant.
>
>  
>
>>I would like to see more discussion of what is "impoverished" about
>>the environments, and what they consider "mainstream programming
>>languages".  Certainly the authors could have discussed this in the
>>main part of the paper?
>>
>>    
>>
>Please read section 5 in the paper.
>
>  
>
>>I'm not sure the authors are even aware or the existence of
>>interactive environments (e.g. Hugs and GHCi are not mentioned, only
(Continue reading)

Permalink | Reply | 0 comments |
headers
Bulat Ziganshin | 1 Sep 2005 13:16

Re[2]: Monadic vs "pure" style (was: pros and cons of sta tic typing and side effects)

Hello Juan,

Thursday, September 01, 2005, 12:03:15 PM, you wrote:

JCAB> instance MyNum Int where
JCAB>     (.+) a b = a + b

JCAB> instance (Monad m, MyNum v) => MyNum (m v) where
JCAB>     (.+) a b = do
JCAB>         ra <- a
JCAB>         rb <- b
JCAB>         return (ra .+ rb)

JCAB>    Just beware: to make this

i think, it is very practical. we can make alternative Prelude, this
question has been already discussed in light of redefining some list
functions (append, head...) as belonging to some Collection class

interestingly that Template Haskell, which uses Q monad to generate
unique identifiers, also use technique of defining rich set of
operations working immediately with monadic values. module
Language.Haskell.TH.Lib is full of definitions like this:

infixP p1 n p2 = do p1' <- p1
                    p2' <- p2
                    return (InfixP p1' n p2')

btw, such definitions can be simplified by using liftM/ap operations:
(Continue reading)

Permalink | Reply | 751 comments |
headers
Jacques Carette | 1 Sep 2005 16:55
Picon
Picon
Favicon

Re: Monadic vs "pure" style


Bulat Ziganshin wrote:

>Language.Haskell.TH.Lib is full of definitions like this:
>
>infixP p1 n p2 = do p1' <- p1
>                    p2' <- p2
>                    return (InfixP p1' n p2')
>
>btw, such definitions can be simplified by using liftM/ap operations:
>
>instance (Monad m, MyNum v) => MyNum (m v) where
>    (.+) = liftM2 (.+)
>  
>
Such simplified forms then occur often enough that, in a scrapping 
boilerplate kind of way, I would really like to be able to write 
something like

instance (Monad m, MyNum v) => MyNum (m v) via lifting
or
lifted instance (Monad m, MyNum v) => MyNum (m v)
or
derived instance (Monad m, MyNum v) => MyNum (m v)

where all the operations from MyNum are obtained via applying the correct arity liftM function from the
Monad class.

Jacques
(Continue reading)

Permalink | Reply | 751 comments |
headers
Frederik Eaton | 1 Sep 2005 23:48

Re: How to debug GHC

On Wed, Apr 27, 2005 at 05:15:30PM +1000, Bernard Pope wrote:
> On Wed, 2005-04-27 at 07:45 +0200, Ketil Malde wrote:
> > > [I want to know] who called who all the way from "main" to "head",
> > > because the key function is going to be one somewhere in the middle.
> > 
> > Perhaps.  I am told stack backtraces are difficult with non-strict
> > semantics.
> 
> This is true, at least for _lazy_ implementations of non-strict
> semantics.
>
> The reason is that the (graph) context in which a function application
> is constructed can be very different to the context in which it is
> reduced. 

Is it that backtraces are difficult, or just require a lot of
overhead? It doesn't seem very hard to me, at least in principle. Add
a "stack trace" argument to every function. Every time a function is
called, the source location of the call is prepended to the "stack
trace". I'm not familiar with the implementation of functional
programming languages, though.

(It seems like if the operation of GHC or GHCI could be parametrized
by an arbitrary monad, here a Reader, then transformations like the
above wouldn't be so difficult, and compiler compatibility for
debuggers wouldn't be so much of an issue.)

> Partial application of functions introduces a similar problem.
>
> This is not a problem in first-order eager languages because the
(Continue reading)

Permalink | Reply | 14 comments |
headers
Mark Goldman | 2 Sep 2005 01:03
Picon

Re: List of functions

On 8/31/05, Krasimir Angelov <kr.angelov <at> gmail.com> wrote:
> 2005/8/31, Sebastian Sylvan <sebastian.sylvan <at> gmail.com>:
> > On 8/31/05, Dinh Tien Tuan Anh <tuananhbirm <at> hotmail.com> wrote:
> > >
> > > >Something like (untested)...
> > > >
> > > >xs <- zipWith ($) forkIO (map (\f -> f x y) funs)
> > > >tids <- sequence xs
> > > >
> > >
> > >
> > > what does "zipWith ($)" do ?
> >
> > $ is function application, so zipWith ($) will "zip" a list of
> > functions with a list of arguments, by applying the functions to the
> > arguments pair-wise, producing a list of results.
> 
> But forkIO is function not a list of functions. The above example is
> incorrect. I think it should be:
> 
> tids <- sequence [forkIO (f x y) | f <- funs]

The following corrects the zipWith example:
xs <- zipWith ($) (repeat forkIO) (map (\f -> f x y) funs)
tids <- sequence xs

--

-- 
"50% of marriages today end in divorce, the other 50% end in death. 
Which would you rather have?"
(Continue reading)

Permalink | Reply | 1 comment |

Gmane