Send Beginners mailing list submissions to
        [email protected]

To subscribe or unsubscribe via the World Wide Web, visit
        http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
        [email protected]

You can reach the person managing the list at
        [email protected]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."


Today's Topics:

   1.  Decomposing recursion (Russ Abbott)
   2. Re:  Decomposing recursion (Stephen Tetley)
   3.  Lifting infix functions in applicative style (Bastian Erdn??)
   4.  Modeling recursive data structs (Nikolay Artamonov)
   5. Re:  Modeling recursive data structs (aditya siram)
   6. Re:  Modeling recursive data structs (Markus L?ll)
   7. Re:  Lifting infix functions in applicative style (Brent Yorgey)


----------------------------------------------------------------------

Message: 1
Date: Fri, 5 Nov 2010 12:51:44 -0700
From: Russ Abbott <[email protected]>
Subject: [Haskell-beginners] Decomposing recursion
To: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"

As someone who comes into contact with Haskell only once a year when I teach
an introductory Haskell course, I'm not familiar with whether the following
is of any general interest.

It struck me that one can decompose recursive functions into their pieces
which can then be plugged into a recursion engine. Define a recursion engine
as follows.

recursionEngine termCond termFn reduceFn mapFn wayAheadFn =
    recursiveFn
    *where *recursiveFn y
            | termCond y = termFn y
            | *otherwise  *= reduceFn (mapFn y) (recursiveFn (wayAheadFn y))

Then one can define, for example, factorial as follows.

factorial =
  recursionEngine
    (==0)     -- *termCond*. Stop when we reach 0
    (\_ -> 1) -- *termFn*. At 0, return 1.
    (*)       -- *reduceFn*. After the recursive call multiply n * factorial
(n-1).
    id        -- *mapFn*. This is what's saved for the reduce function.
    (+ (-1))  -- *wayAheadFn*.  The recursive call is made on n-1.

What I like about this is that it abstracts out the recursive process and
allows one to plug functions into it to achieve what one wants.  This is
similar in spirit to map, foldr, and similar higher order functions.

I'm writing because I like this and wanted to share it. Also, the standard
higher order functions are, or course, widely used. My question is whether
this has been pushed further to generate widely used libraries of other
higher order functions and if so whether there is a discussion of them
somewhere. In other words, what other algorithmic frameworks have been
abstracted in this way?  (I wouldn't count, for example, sort and zip since
only one function is plugged into their abstract versions; changing that
function doesn't significantly change the *kind *of computation being
done.) Although it's hard to tell, I didn't see anything that looked similar
in either the libraries that come with the standard Haskell download or on
hackage <http://hackage.haskell.org/packages/archive/pkg-list.html>.

This wiki 
page<http://cs.calstatela.edu/wiki/index.php/Courses/CS_332F/Recursion_engines>is
my presentation of this. Besides a recursionEngine it also includes a
tailRecursionEngine (for tail recursion, naturally) and an
extendedRecursionEngine. The extendedRecursionEngine supports functions that
require multiple recursive calls in the body such as mergesort or quicksort.

Thanks.
*
-- Russ Abbott
_____________________________________________*
*  Professor, Computer Science
  California State University, Los Angeles

  Google voice: 424-235-5752 (424-cell-rja)
  blog: http://russabbott.blogspot.com/
  vita:  http://sites.google.com/site/russabbott/
_____________________________________________*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
http://www.haskell.org/pipermail/beginners/attachments/20101105/c59a53a9/attachment-0001.html

------------------------------

Message: 2
Date: Fri, 5 Nov 2010 20:54:52 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Decomposing recursion
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

Hello Russ

Richard Kieburtz has a slightly smaller formulation of primitive
recursion on page 13 of these slides - the fold-like argument 'h'
doesn't appear to need a change of type:

http://programatica.cs.pdx.edu/P/Programatica%20Logic1.pdf

genPR :: (a -> Bool) -> (a -> a) -> c -> (a -> c -> c) -> a -> c
genPR p b g h x = if p x then g else h x (genPR p b g h (b x))


-- factorial function:
fact :: Integer -> Integer
fact = genPR (==0) (subtract 1) 1 (*)

Ignoring changes in argument order, the type of your recursionEngine
is one term and one type variable larger:

recursionEngine :: (a -> Bool) -> (a -> c) -> (b -> c -> c) -> (a ->
b) -> (a -> a)-> a -> c

Best wishes

Stephen


------------------------------

Message: 3
Date: Sat, 6 Nov 2010 01:33:39 +0100
From: Bastian Erdn?? <[email protected]>
Subject: [Haskell-beginners] Lifting infix functions in applicative
        style
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii

When I want to lift an infix function into an applicative functor I use 
'liftA2' -- I just call it 'up' for the sake of brevity.  But I always have to 
add some parenthesis since I don't know how to tell Haskel that `up op` shall 
have the same fixity as `op` has.  Is there a way to do that?

Cheers,
Bastian



------------------------------

Message: 4
Date: Sat, 6 Nov 2010 06:37:42 +0300
From: Nikolay Artamonov <[email protected]>
Subject: [Haskell-beginners] Modeling recursive data structs
To: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

Hi all! How can we model in Haskell three hypothetic data structures
A, B, C which obey following conditions:

1. A is anything
2. B is list of A's
3. C is list of A's or B's or another C's

So, for example, it would be possible to write something like: C [A, B
[A, A], A, C [A, B [A]]].

I wrote this code:

data Super = A | B [A] | C[Super]

Not surprisingly, Haskell refused to accept subexpression `B[A]`,
because "Not in scope: type constructor or class `A'". How to solve
this problem?

More "real" example of A, B and C:

data Shape = Point Int Int | Polyline [Point] | Shape [Shape]

Interestingly, if I replace Polyline [Point] to Polyline [Shape] then
definition will be accepted. But what if I want *polylines* consists
of *points*, not any *shapes*?

Thank you!

-- 
Nikolay Artamonov


------------------------------

Message: 5
Date: Fri, 5 Nov 2010 23:14:12 -0500
From: aditya siram <[email protected]>
Subject: Re: [Haskell-beginners] Modeling recursive data structs
To: Nikolay Artamonov <[email protected]>
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

Does the following code help?

type Point = (Int,Int)
type PolyLines = [Point]
data Shape = Point Point | PolyLines PolyLines | Shape [Shape]
-- here you might want to write:
-- data Shape = Point | PolyLines | [Shape]
-- but Haskell requires that "type constructors" like "data Shape ..."
-- use "data constructors" like "Point ...", "PolyLines ..." to group
-- different values.
-- Type synonyms, however, don't require a data constructor but
-- are restricted to one value

-- Example usage :
shapes = Shape [(Point (1,2)), PolyLines [(2,3),(4,5)],
Shape[Shape[Point (6,7)]]]

-deech

On Fri, Nov 5, 2010 at 10:37 PM, Nikolay Artamonov <[email protected]> wrote:
> Hi all! How can we model in Haskell three hypothetic data structures
> A, B, C which obey following conditions:
>
> 1. A is anything
> 2. B is list of A's
> 3. C is list of A's or B's or another C's
>
> So, for example, it would be possible to write something like: C [A, B
> [A, A], A, C [A, B [A]]].
>
> I wrote this code:
>
> data Super = A | B [A] | C[Super]
>
> Not surprisingly, Haskell refused to accept subexpression `B[A]`,
> because "Not in scope: type constructor or class `A'". How to solve
> this problem?
>
> More "real" example of A, B and C:
>
> data Shape = Point Int Int | Polyline [Point] | Shape [Shape]
>
> Interestingly, if I replace Polyline [Point] to Polyline [Shape] then
> definition will be accepted. But what if I want *polylines* consists
> of *points*, not any *shapes*?
>
> Thank you!
>
> --
> Nikolay Artamonov
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>


------------------------------

Message: 6
Date: Sat, 6 Nov 2010 12:01:30 +0200
From: Markus L?ll <[email protected]>
Subject: Re: [Haskell-beginners] Modeling recursive data structs
To: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

Try this: data Super a = A a | B [a] | C [Super a]

--
Markus Läll

On Sat, Nov 6, 2010 at 6:14 AM, aditya siram <[email protected]> wrote:
> Does the following code help?
>
> type Point = (Int,Int)
> type PolyLines = [Point]
> data Shape = Point Point | PolyLines PolyLines | Shape [Shape]
> -- here you might want to write:
> -- data Shape = Point | PolyLines | [Shape]
> -- but Haskell requires that "type constructors" like "data Shape ..."
> -- use "data constructors" like "Point ...", "PolyLines ..." to group
> -- different values.
> -- Type synonyms, however, don't require a data constructor but
> -- are restricted to one value
>
> -- Example usage :
> shapes = Shape [(Point (1,2)), PolyLines [(2,3),(4,5)],
> Shape[Shape[Point (6,7)]]]
>
> -deech
>
> On Fri, Nov 5, 2010 at 10:37 PM, Nikolay Artamonov <[email protected]> 
> wrote:
>> Hi all! How can we model in Haskell three hypothetic data structures
>> A, B, C which obey following conditions:
>>
>> 1. A is anything
>> 2. B is list of A's
>> 3. C is list of A's or B's or another C's
>>
>> So, for example, it would be possible to write something like: C [A, B
>> [A, A], A, C [A, B [A]]].
>>
>> I wrote this code:
>>
>> data Super = A | B [A] | C[Super]
>>
>> Not surprisingly, Haskell refused to accept subexpression `B[A]`,
>> because "Not in scope: type constructor or class `A'". How to solve
>> this problem?
>>
>> More "real" example of A, B and C:
>>
>> data Shape = Point Int Int | Polyline [Point] | Shape [Shape]
>>
>> Interestingly, if I replace Polyline [Point] to Polyline [Shape] then
>> definition will be accepted. But what if I want *polylines* consists
>> of *points*, not any *shapes*?
>>
>> Thank you!
>>
>> --
>> Nikolay Artamonov
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>


------------------------------

Message: 7
Date: Sat, 6 Nov 2010 06:22:50 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Lifting infix functions in
        applicative style
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1

On Sat, Nov 06, 2010 at 01:33:39AM +0100, Bastian Erdnüß wrote:
> When I want to lift an infix function into an applicative functor I use 
> 'liftA2' -- I just call it 'up' for the sake of brevity.  But I always have 
> to add some parenthesis since I don't know how to tell Haskel that `up op` 
> shall have the same fixity as `op` has.  Is there a way to do that?
> 

No, there isn't.  Also, `up op` is not valid syntax -- only names may
go in between `backticks`, not expressions in general.

You may be interested in the InfixApplicative package:

  http://hackage.haskell.org/package/InfixApplicative

although it still doesn't solve the problem of fixity.

-Brent


------------------------------

_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners


End of Beginners Digest, Vol 29, Issue 7
****************************************

Reply via email to