fold over list of tuples
falcon
programming. I'm fairly comfortable with the basics of fold, map, etc.
For example, [fold + 0 list] will sum up a list or [fold * 1 list]
will return a product of a list (this is pseudo code, obviously).
I don't understand exactly how fold can be used when a list consits of
tuples, rather than simple integers or floats. How does the fold
operator know which attribute of the tuple I want calculated?
Obviously I can pass an expression to fold which knows about the tuple
and only picks the attribute it needs, but I'm trying to keep the
functions general! Do I have to deal with zip/unzip? Is the fold
syntax extended to allow of another parameter signifying the attribute
of a tuple [fold + 0 3 list] (sum list on tuple's attribute 3, ...but
how can a sigle attribute of a tuple be reduced...all of them have to
be reduced). eh...I'm a little confused. Look forward to some
answers. Thanks!
Greg Buchholz
> I don't understand exactly how fold can be used when a list consits of
> tuples, rather than simple integers or floats. How does the fold
> operator know which attribute of the tuple I want calculated?
> Obviously I can pass an expression to fold which knows about the tuple
> and only picks the attribute it needs, but I'm trying to keep the
> functions general! Do I have to deal with zip/unzip?
-- Haskell code. Probably not exactly what you want, but a start...
main =
do -- First, a simple sum. Almost like pseudo-code.
print (foldl (+) 0 list)
-- The obvious way, deconstructing tuple inside fold
print (foldl (\acc elem -> acc + third elem) 0 t_list)
-- Using unzip3 to make a list of tuples into tuple of lists
print (foldl (+) 0 ((third.unzip3) t_list))
-- Operating on everything inside the tuple, all at once
print (foldr (\(x,y,z) (a,b,c) -> (x++a,y*b,z+c))
("",1.0,0) t_list)
list = [1..10]
t_list = [("foo", 3.14, 1),
("bar", 2.78, 2),
("baz", 1.41, 3)]
third (a,b,c) = c
Dinko Tenev
> I understand the 'fold' operator is extremely powerful in functional
> programming. I'm fairly comfortable with the basics of fold, map, etc.
> For example, [fold + 0 list] will sum up a list or [fold * 1 list]
> will return a product of a list (this is pseudo code, obviously).
>
> I don't understand exactly how fold can be used when a list consits of
> tuples, rather than simple integers or floats.
Exactly the same, save that you can't do to tuples what you can do to
ints or floats. Nevertheless, tuples are values too, so you can fold a
list of tuples by any function that takes two tuples and produces a
tuple of the same size, or by a function that takes a thingie and a
tuple, and produces a thingie, depending on the particular flavor(s) of
fold you have.
> How does the fold
> operator know which attribute of the tuple I want calculated?
My guess is that, by "fold operator," you mean the first argument of
fold. Most of the time, it wouldn't _know_ anything -- it would rather
have certain _expectations_ for its arguments, and _you_ are supposed
to know what list can be folded by what binary op.
> Obviously I can pass an expression to fold which knows about the tuple
> and only picks the attribute it needs, but I'm trying to keep the
> functions general!
That would essentially be missing the point, so it's a good thing that
you're having second thoughts about it ;)
> Do I have to deal with zip/unzip?
You can, but you don't have to.
> Is the fold
> syntax extended to allow of another parameter signifying the attribute
> of a tuple [fold + 0 3 list] (sum list on tuple's attribute 3, ...but
> how can a sigle attribute of a tuple be reduced...all of them have to
> be reduced). eh...I'm a little confused. Look forward to some
> answers. Thanks!
Fold has nothing to do with syntax -- it's just a function (well, a
higher-order one.)
BTW, I have the feeling that you may be living in the dynamically-typed
world. If you would care to tell us where exactly your notion of fold
comes from, it could make explanations easier.
Cheers,
Dinko
falcon
than lisp to the model in my head. I'm investigating fold on tuples
because of some papers I read regarding foldr being the main function
needed to simulate sql (in the form of list comprehensions or monad
comprehensions). I am having a hard time developing an intuitive feel
for fold over tuples.
Neelakantan Krishnaswami
wrote:
Study the type of fold:
fold : (a -> b -> b) -> b -> List a -> b
The first argument to the fold function -- what you call the fold
operator -- is of type a -> b -> b. The type a is the the type of
the elements of the list, and the second argument is the type of
the result value you're going to return.
In the case of (fold (+) 0 list), what are the argument types?
(+) : Int -> Int -> Int
0 : Int
list : List Int
In this case a = Int and b = Int.
Now, let's suppose that we have a list of pairs of integers and
strings, and want to add the first element of each list. We can
do that with the call to fold (fold addfirst 0 list2), where
we can define addfirst as:
fun addfirst (num, str) total = num + total
What are the types?
addfirst : (Int * String) -> Int -> Int
0 : Int
list2 : List (Int * String)
Now, a = (Int * String), and b = int.
--
Neel Krishnaswami
ne...@cs.cmu.edu
Dinko Tenev
I think your difficulty comes from the expectation that fold should be
aware of the structure of tuples themselves, which is not the case.
Fold only knows about the structure of the list you are folding, and it
doesn't care about the structure or behavior of individual elements --
that only concerns the function you are folding with (given to fold as
the first argument.)
Cheers,
Dinko
Stefan Axelsson
> I'm investigating fold on tuples
> because of some papers I read regarding foldr being the main function
> needed to simulate sql (in the form of list comprehensions or monad
> comprehensions). I am having a hard time developing an intuitive feel
> for fold over tuples.
You might want to have a look at: "A tutorial on the universality and
expressiveness of fold", Graham Hutton. Journal of Functional
Programming, 9(4):355-372, online at the author's homepage:
http://www.cs.nott.ac.uk/~gmh/bib.html
Stefan,
--
Stefan Axelsson (email at http://www.cs.chalmers.se/~sax)
Jon Harrop
> I understand the 'fold' operator is extremely powerful in functional
> programming. I'm fairly comfortable with the basics of fold, map, etc.
> For example, [fold + 0 list] will sum up a list or [fold * 1 list]
> will return a product of a list (this is pseudo code, obviously).
In real OCaml code:
# let sum list = List.fold_left ( + ) 0 list;;
val sum : int list -> int = <fun>
> I don't understand exactly how fold can be used when a list consits of
> tuples, rather than simple integers or floats.
Consider rewriting the previous example a little more verbosely:
# let sum list = List.fold_left (fun s x -> s+x) 0 list;;
val sum : int list -> int = <fun>
The supplied function acts on two ints called "s" and "x".
The "sum" function can be used like this:
# sum [1;2;3];;
- : int = 6
> How does the fold operator know which attribute of the tuple I want
> calculated?
No, you have to "tell it" which field of the tuple you want. This is most
easily done for tuples using a pattern. In this case, replace "s" and "x"
with patterns that deconstruct your tuple. For example, to sum a list of
pairs of integers:
# let sum_pairs list =
List.fold_left (fun (s1, s2) (x1, x2) -> (s1+x1, s2+x2)) (0, 0) list;;
val sum_pairs : (int * int) list -> int * int = <fun>
Here, "(s1, s2)" and "(x1, x2)" are the patterns.
This function can be used like this:
# sum_pairs [(1, 2); (2, 3); (3, 4)];;
- : int * int = (6, 9)
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
falcon
falcon
paragraphs, I'll give it another try. Thanks.
Jon Harrop
> Thanks, I started with SML code recently.
Here's an SML port:
- fun sum list = foldl (op +) 0 list;
val sum = fn : int list -> int
> I don't understand exactly how fold can be used when a list consits of
> tuples, rather than simple integers or floats.
Consider rewriting the previous example a little more verbosely:
- fun sum list = foldl (fn (s, x) => s+x) 0 list;
val sum = fn : int list -> int
The supplied function acts on two ints called "s" and "x".
The "sum" function can be used like this:
- sum [1, 2, 3];
val it = 6 : int
> How does the fold operator know which attribute of the tuple I want
> calculated?
No, you have to "tell it" which field of the tuple you want. This is most
easily done for tuples using a pattern. In this case, replace "s" and "x"
with patterns that deconstruct your tuple. For example, to sum a list of
pairs of integers:
# fun sum_pairs list =
foldl (fn ((s1, s2), (x1, x2)) => (s1+x1, s2+x2)) (0, 0) list;
val sum_pairs = fn : (int * int) list -> int * int
Here, "(s1, s2)" and "(x1, x2)" are the patterns.
This function can be used like this:
# sum_pairs [(1, 2), (2, 3), (3, 4)];
val it = (6,9) : int * int
falcon
> easily done for tuples using a pattern. In this case, replace "s" and "x"
> with patterns that deconstruct your tuple
Right, that was the part I had trouble with. My list may have tuples
with arbitrary cardinality. I'm specifically thinking of database
table queries where aggregate functions can be applied to any column
(of appropriate type)....actually as I type this I think I understand
another approach. Just need to try out the code :) Thanks.
Jon Harrop
>> No, you have to "tell it" which field of the tuple you want. This is most
>> easily done for tuples using a pattern. In this case, replace "s" and "x"
>> with patterns that deconstruct your tuple
>
> Right, that was the part I had trouble with. My list may have tuples
> with arbitrary cardinality.
There is no such thing as a "tuple with arbitrary cardinality" in ML. You
probably mean a list.
> I'm specifically thinking of database
> table queries where aggregate functions can be applied to any column
> (of appropriate type)....actually as I type this I think I understand
> another approach. Just need to try out the code :) Thanks.
Sounds like you want to use a pattern like [_, x, _] or _::x::_ and a
catch-all clause that raises an exception if the list is not of the proper
form.
falcon
question was regarding how to use folds over a list of tuples. I think
my problem is actually figuring out the best way to use 'projection.'
Given a list of tuples, I need to traverse the list and either remove
an attribute or add a new one (the new one will most likely be
calculated using existing attributes). For example:
'('("John" 21 1000) <==(name age networth)
'("Jim" 32 50000)
'("Jack" 27 15000))
1. I may need to remove 'age' from each tuple
2. I may need to add an attribute calculated with : netwroth+age
(whatever that means)
3. I may need to add the current date (so here I'm adding an attribute
which does not depend on existing attributes).
(basically I'm hoping to slowly build up a mini-sql database, I've read
some academic papers but it is not so easy to translate them into
actual working code)
So, my first guess is to build a high order function 'project' which
takes as parameters a list of parameters which should be removed, then
cons together all such attributes from the source tuple (I'll be given
each tuple since I'll pass this function to 'map'). I'll need a
seperate function 'extend' which will take a list of attributes and a
list of functions to apply to those attributes, then the results will
be consed together (although I'm not sure what to do if more than one
function needs to be appllied...abs(round(celi(floor(x))) ).
Since such operations seem to be so basic, I'm wondering if I haven't
missed anything obvious. I keep reading about
map/fold/zip/unzip/filter/etc. Is there a well thought out way of
implementing my 'project' and 'extend' functions as well?
As I mentioned earlier, once I have all these functions, my next step
will be to parse a simple sql expression (passed in during run-time)
and 'execute' it against a list of 'columns.' But that is still quite
far away :)
Dinko Tenev
manipulating a list of heterogeneous lists.
Given your goal of building-up a DB, I would suggest defining Table and
Row abstractions with suitable interfaces (you appear to be halfway
there, anyway,) and only then sit down and think about the
implementation.
The reason you need this is that, if you're supposed to extend your
"tuples" (rows) in a way that's decided at run-time, then you'd
probably need to store some type-info somewhere. One way is to store
it on a per row basis, but that would be outrageous waste of memory.
You should rather store it once, and make sure that both row data and
row type info are always available simultaneously. The easiest way to
do this is to pack them together and hide them behind an interface.
Cheers,
Dinko
Greg Buchholz
> Ok, an update. I've been experimenting with Scheme. My earlier
> question was regarding how to use folds over a list of tuples. I think
> my problem is actually figuring out the best way to use 'projection.'
> Given a list of tuples, I need to traverse the list and either remove
> an attribute or add a new one (the new one will most likely be
> calculated using existing attributes). For example:
> Since such operations seem to be so basic, I'm wondering if I haven't
> missed anything obvious. I keep reading about
> map/fold/zip/unzip/filter/etc. Is there a well thought out way of
> implementing my 'project' and 'extend' functions as well?
;;; Maybe the simple answer you are looking for are association lists?
;;; http://srfi.schemers.org/srfi-1/srfi-1.html#AssociationLists
;;;
;do a song and dance to get sfri-1 loaded...
(require (lib "1.ss" "srfi")) ;DrScheme
;(require-extension srfi-1) ;Chicken
(define data-base
'(((name . "John") (age . 21) (net-worth . 1000 ))
((name . "Jim") (age . 32) (net-worth . 50000))
((name . "Jack") (age . 27) (net-worth . 15000))))
(define (pretty-print records)
(begin
(for-each (lambda (n)
(begin
(display n)
(newline))) records)
(newline)))
;;; 1. I may need to remove 'age' from each tuple
(pretty-print (map (lambda (record)
(alist-delete 'age record eq?))
data-base))
;;; 2. I may need to add an attribute calculated with : networth+age
;;; (whatever that means)
(pretty-print (map (lambda (record)
(alist-cons
'networth+age
(+ (cdr (assoc 'age record))
(cdr (assoc 'net-worth record)))
record))
data-base))
;;; 3. I may need to add the current date (so here I'm adding an
;;; attribute which does not depend on existing attributes).
(define current-date "11/17/2005") ; or whatever
(pretty-print (map (lambda (record)
(alist-cons
'date
current-date
record))
data-base))
Stephan Hohe
> (although I'm not sure what to do if more than one
> function needs to be appllied...abs(round(celi(floor(x))) ).
I don't know Scheme, but there is for sure some function composition
operator that can combine functions in the way you want here. In Haskell
this would be "." and above function would just be
(abs . round . celi . floor)
/Stephan
Marcin 'Qrczak' Kowalczyk
A more general and more direct way is to pass
(lambda (x) (abs (round (ceil (floor x)))))
as the function.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/