地图，过滤器和累加器 [英] Maps, filters and accumulators
问题描述
用于实现地图，过滤器和
累加器的C语言有多好？
SCHEME程序员可以将过程作为参数传递/>
很容易，而C程序员会 - 我猜 - 使用variadic
函数指针，坦率地说这很恶心，我甚至不确定我是否需要
想以这种方式坐下来破解语言。
你的想法？你可以推荐我的任何图书馆吗？
干杯，马特
How good is the C language for implementing maps, filters and
accumulators?
SCHEME programmers would be able to pass procedures as arguments quite
easily, whereas C programmers would - I guess - have use variadic
function pointers which is frankly disgusting, and I''m not even sure I
want to sit down and hack at the language in that way.
Your thoughts? Any libraries you could refer me to?
Cheers, Matt
推荐答案
文章< 11 ********************** @ i3g2000cwc.googlegroups。 com>，
ballpointpenthief< ba *************** @ yahoo.co.ukwrote：
In article <11**********************@i3g2000cwc.googlegroups. com>,
ballpointpenthief <ba***************@yahoo.co.ukwrote:
>用于实现地图，过滤器和
累加器的C语言有多好？
SCHEME程序员可以很容易地将过程作为参数传递，而C程序员会 - 我猜 - 使用variadic
函数指针，坦率地说这很恶心，而且我甚至不确定我是否想以这种方式坐下来破解语言。
你的想法？你能引用我的任何图书馆？
>How good is the C language for implementing maps, filters and
accumulators?
SCHEME programmers would be able to pass procedures as arguments quite
easily, whereas C programmers would - I guess - have use variadic
function pointers which is frankly disgusting, and I''m not even sure I
want to sit down and hack at the language in that way.
Your thoughts? Any libraries you could refer me to?
C程序员可以通过（几乎）
向函数传递指针，这与Scheme程序员可以自己传递函数相同，
并且可以以相同的方式使用它们。
C没有匿名函数或闭包，你可能会错过那些，
但是匿名函数是仅的。一个符号方便（如果有时候是
a主要的！）和闭包可以伪造，如果你控制接口
沿着最终调用函数的整个调用者链，
将一个指针传递给一个结构，该结构包含任何需要比函数的单个调用持续时间长的
的结构。
它们不一定是变量函数（并试图这样做）
会使它不必要地变得更加丑陋），但你必须要更多
小心与您的数据结构。 Scheme已经链接了
语言中内置的列表，这使得处理值列表变得更加容易。在C
中，您可以构建自己的链接列表，但是使用
数组通常更自然地用于您使用列表的各种事物用一种蹩脚的语言。
这里有一些例子（希望）让你开始。不要让
措辞吓跑你;其中大部分是因为C
有静态类型，需要在你使用它之前声明所有内容，并且一旦理解它就变得相当简单。
从底部开始并在第一次工作时可能更有用
你读到这个，因为之前的东西主要是设置为
最后有趣的东西。
标准免责声明适用：未编译或测试。仅用于解释
目的。你会毫不费力地找到聪明的人，他们不同意我所说的一切（虽然希望你能找到与我同意的智能人士并不是很难） 。不要相信任何人
谁在周五晚上发布到usenet。
--------
/ ******************* * *******************
*我们正在使用的一些typedef。 *
*在实际代码中我可能不会理会这些，但它会使*
*更清楚地用于演示目的（特别是因为*
*我使用相同类型的计数器和其他簿记作为实际数据*
*。 *
***************************************** ********* ******************* /
/ *这是实际的类型我们正在使用的数据元素。* /
typedef int my_data_type;
/ * C没有本机布尔类型。经常做这样的事情
并没有让事情变得更加清晰，并且可能会引起可怕的滥用，但是对于
短片的演示目的，它会使意图更清晰。 />
* /
typedef int boolean;
/ * Typedefing函数指针使事情更容易阅读如果你是
仍在努力绕过它们，但是学习阅读
没有typedef的函数指针声明值得花时间
如果你正在使用他们经常。
* /
/ * trans_func_c是一个指向函数的指针，该函数接受my_data_type
并返回另一个my_data_type （对地图很有用）。
（trans ==" transform"，_ c后缀表示它有一个cookie参数）
cookie参数用于将信息传递给函数
（伪造一个闭包）。如果该函数不需要任何外部
信息，则可以忽略它。
* /
typedef my_data_type（* trans_func_c）（ my_data_type in，void * cookie）;
/ * pred_func是指向某个值的谓词函数的指针
（对于过滤器很有用）
* /
typedef boolean（* pred_func）（my_data_type in）;
/ * binary_func是指向值<的二元运算符的指针br />
（折叠很有用）
* /
typedef my_data_type（* binary_func）（my_data_type left，my_data_type right）;
/ ******************************************* ******* ***********************
*这些是真正的功能做所有的工作。一旦你得到*
*接口正确（这可能需要几次尝试才能得到*
*你需要的一切但不要忘记如何使用它们） *
*这些只需要写一次。 *
***************************************** ********* *********************** /
/ *所有这些都使用数组他们工作的清单。来电是
负责管理所有内存。
* /
/ *请注意，必须为您计划使用的每种类型编写这些内容他们使用（和，对于那些可以合理使用多种类型的用户，每种类型的组合使用
）。
C ++模板可能会如果你想使用几种不同的数据类型，这会更容易，但是对于少数类型的这种类型来说这样做
方式可以正常工作。 （这些很简单，也很专业，如果你不想使用C ++，你可以写一个代码生成器为你想要的
类型生成C代码只是为了获得模板。）
即使使用模板，类型仍然需要静态知道
编译时间。实现真正的动态类型可能是非常丑陋的，你最好找到一个可嵌入的
方案解释器。
* /
/ * Map：dest [i] = func（src [i]）for all 0< = i< num_in * /
void map_c（const my_data_type * src，my_data_type * dest，int num_in，
trans_func_c func，void * cookie）
{
int i;
for（i = 0; i< num_in; i ++）
dest [i] =（* func）（src [i]，cookie）;
}
/ *过滤器：dest []填充了src []的元素，其中
pred（）返回true，按照它们出现在src []中的顺序。
返回复制到dest []的元素数。
* /
int filter（const my_data_type * src，my_data_type * dest， int num_in，
pred_func pred）
{
int i;
int num_out = 0;
for（i = 0; i< num_in; i ++）
if（（* pred）（src [i]））
dest [num_out ++] = src [i];
返回num_out;
}
/ *折叠：按顺序将op应用于累加器和src [i]。
返回最终值累加器。
* /
my_data_type fold（const my_data_type * src，int num_in，
binary_func op，my_data_type acc）
{
int i;
for（i = 0; i< num_in; i ++）
acc = op（acc，src [i]）;
返回acc;
}
/ **************** ********************************** **************** ******
*以上所有内容都可以重复使用（但是你可能想写一下*
*它只需要几次写入以确保你理解接下来会发生什么*
*并且在界面上有足够但不太多的通用性。 *
*接下来是我们为地图，过滤和折叠提供的功能。 *
***************************************** ********* ********************** /
/ *加法器。 cookie参数需要是指向我们要添加的值
的指针。
这是一个我们可以将trans_func_c指向的函数。
* /
my_data_type add（my_data_type val，void * vcookie）
{
my_data_type * cookie = vcookie;
返回val + * cookie;
}
/ *值是否均等？
这是我们可以使用的功能将pred_func指向。
* /
boolean is_even（my_data_type val）
{
return（val％ 2）== 0;
}
/ *添加两个值。
这是一个我们可以指向binary_func的函数at。
* /
my_data_type plus（my_data_type left，my_data_type right）
{
返回左+右;
}
/ ******************************* ******************* ******
*现在我们已经设置了所有内容，让我们展示它关闭。 *
***************************************** ********* ****** /
#include< stdio.h>
void print_array （const my_data_type * arr，int num）
{
int i;
for（i = 0; i< num; i ++）
printf（"％d"，arr [i]）;
printf（" \ n"）;
}
int main（无效）
{
const my_data_type src [] = {0,1,2,3,4， 5,6,7,8,9,10};
const int num_src = sizeof src / sizeof * src;
my_data_type dest [sizeof src / sizeof * src] ;
int num_dest;
my_data_type to_add;
printf（" src []："）;
print_array（src，num_src）;
/ *为所有内容添加17 * /
to_add = 17;
map_c（src，dest，num_src，add，& to_add）;
num_dest = num_src; / * map（）没有改变或报告大小* /
printf（" After map（）："）;
print_array（dest，num_dest） ;
/ *过滤偶数* /
num_dest = filter（src，dest，num_src，is_even）;
printf（" After filter（）："）;
print_array（dest，num_dest）;
/ *整个列表中的折叠加*
printf（"所有值的总和：％d \ n"，fold（src，num_src，plus，0））;
/ *折叠加法过滤list * /
printf（偶数值之和：％d \ n，折叠（dest，num_dest，加号，0））;
返回0;
}
--------
dave
-
Dave Vandervies dj ****** @ csclub.uwaterloo.ca
我当然认为如果程序员在Scheme中编程，那么他就知道Scheme。
--Joe Marshall in comp.lang .scheme
C programmers can pass pointers to functions around with (almost) the
same ease that Scheme programmers can pass the functions themselves,
and can use them in much the same way.
C doesn''t have anonymous functions or closures, and you may miss those,
but anonymous functions are "only" a notational convenience (if sometimes
a major one!) and closures can be faked, if you control the interfaces
along the entire chain of callers that ends up invoking the function,
by passing a pointer to a struct containing anything that needs to last
longer than a single invocation of the function.
They don''t have to be variadic functions (and trying to do it that way
would make it unnecessarily much uglier), but you do have to be more
careful with your data structures. Scheme has linked lists built into the
language, which makes dealing with lists of values Rather Easier. In C
you could build your own linked lists, but it''s often more natural to use
arrays for the sorts of things you''d use a list for in a lispy language.
Here''s some examples to (hopefully) get you started. Don''t let the
verbiage scare you off; most of it is a consequence of the fact that C
has static typing and requires everything to be declared before you use
it, and becomes fairly simple once you understand it.
It may be more useful to start at the bottom and work up the first time
you read this, since the earlier stuff is mostly just setting up for
the interesting stuff at the end.
Standard disclaimers apply: Not compiled or tested. For explanatory
purposes only. You will have no trouble finding intelligent people who
disagree with everything I say (though hopefully it''s not too hard to
find intelligent people who agree with me either). Don''t trust anybody
who''s posting to usenet on a Friday night.
--------
/************************************************** *******************
* Some typedefs for what we''re working with. *
* In real code I would probably not bother with these, but it makes *
* things clearer for demonstration purposes (especially since *
* I''m using the same type for counters and other bookkeeping as *
* for the actual data). *
************************************************** *******************/
/*This is the type of the actual data elements we''re working with.*/
typedef int my_data_type;
/*C doesn''t have a native boolean type. Doing something like this often
doesn''t make things any clearer and can invite horrible abuse, but for
demonstration purposes in short chunks it makes the intent clearer.
*/
typedef int boolean;
/*Typedefing function pointers makes things A LOT easier to read if you''re
still working on wrapping your head around them, but learning to read
function pointer declarations without the typedefs is worth your time
if you''ll be working with them regularly.
*/
/*trans_func_c is a pointer to a function that takes a my_data_type
and returns another my_data_type (useful for map).
(trans=="transform", _c suffix means it has a cookie argument)
The "cookie" argument is used to pass information to the function
(faking a closure). If the function doesn''t need any external
information, it can be ignored.
*/
typedef my_data_type (*trans_func_c)(my_data_type in,void *cookie);
/*pred_func is a pointer to a predicate function on some value
(useful for filter)
*/
typedef boolean (*pred_func)(my_data_type in);
/*binary_func is a pointer to a binary operator on values
(useful for fold)
*/
typedef my_data_type (*binary_func)(my_data_type left,my_data_type right);
/************************************************** ***********************
* These are the functions that "really" do all the work. Once you get *
* the interfaces right (which will probably take a few tries to get *
* everything you need but not so much you forget how to use them) *
* these only have to be written once. *
************************************************** ***********************/
/*All of these use arrays for the lists they work on. Caller is
responsible for managing all memory.
*/
/*Note that these have to be written for every type you plan to use them
with (and, for ones that can sensibly work with multiple types, for
every combination of types).
C++ templates may make this easier if you want to work with several
different data types, but for a small number of types doing it this
way will work fine. (These are simple and specialized enough that
you could probably write a code generator to produce C code for the
types you want if you don''t want to use C++ just to get templates.)
Even with templates the types still need to be statically known at
compile time. Implementing true dynamic typing is probably
sufficiently ugly that you''d be better off finding an embeddable
Scheme interpreter.
*/
/*Map: dest[i]=func(src[i]) for all 0<=i<num_in*/
void map_c(const my_data_type *src, my_data_type *dest, int num_in,
trans_func_c func, void *cookie)
{
int i;
for(i=0;i<num_in;i++)
dest[i]=(*func)(src[i],cookie);
}
/*Filter: dest[] is populated with the elements of src[] for which
pred() returns true, in the order in which they appear in src[].
Returns the number of elements copied to dest[].
*/
int filter(const my_data_type *src,my_data_type *dest,int num_in,
pred_func pred)
{
int i;
int num_out=0;
for(i=0;i<num_in;i++)
if((*pred)(src[i]))
dest[num_out++]=src[i];
return num_out;
}
/*Fold: Apply op to accumulator and src[i] for each i in order.
Return final value of accumulator.
*/
my_data_type fold(const my_data_type *src,int num_in,
binary_func op,my_data_type acc)
{
int i;
for(i=0;i<num_in;i++)
acc=op(acc,src[i]);
return acc;
}
/************************************************** **********************
* Everything above this can be re-used (but you probably want to write *
* it longhand a few times to make sure you understand what''s going *
* on and have enough-but-not-too-much generality in the interface). *
* Next comes the functions we''re giving to map, filter, and fold. *
************************************************** **********************/
/*An adder. The cookie argument needs to be a pointer to the value
we want to add.
This is a function we can point a trans_func_c at.
*/
my_data_type add(my_data_type val,void *vcookie)
{
my_data_type *cookie=vcookie;
return val + *cookie;
}
/*Is a value even?
This is a function we can point a pred_func at.
*/
boolean is_even(my_data_type val)
{
return (val%2)==0;
}
/*Add two values.
This is a function we can point a binary_func at.
*/
my_data_type plus(my_data_type left,my_data_type right)
{
return left+right;
}
/************************************************** ******
* Now that we''ve set everything up, let''s show it off. *
************************************************** ******/
#include <stdio.h>
void print_array(const my_data_type *arr,int num)
{
int i;
for(i=0;i<num;i++)
printf("%d ",arr[i]);
printf("\n");
}
int main(void)
{
const my_data_type src[]={0,1,2,3,4,5,6,7,8,9,10};
const int num_src=sizeof src / sizeof *src;
my_data_type dest[sizeof src / sizeof *src];
int num_dest;
my_data_type to_add;
printf("src[]: ");
print_array(src,num_src);
/*Add 17 to everything*/
to_add=17;
map_c(src,dest,num_src,add,&to_add);
num_dest=num_src; /*map() doesn''t change or report size*/
printf("After map(): ");
print_array(dest,num_dest);
/*Filter for the even ones*/
num_dest=filter(src,dest,num_src,is_even);
printf("After filter(): ");
print_array(dest,num_dest);
/*Fold addition over entire list*/
printf("Sum of all values: %d\n",fold(src,num_src,plus,0));
/*Fold addition over filtered list*/
printf("Sum of even values: %d\n",fold(dest,num_dest,plus,0));
return 0;
}
--------
dave
--
Dave Vandervies dj******@csclub.uwaterloo.ca
I certainly assume that if the programmer is programming in Scheme,
then he knows Scheme.
--Joe Marshall in comp.lang.scheme
[感谢Dave Vandervies，这是最有用的信息
我曾在USENET上读过。]
它仍然无法使用
base_types的arbritrary数量？可以轻松设置所有内容以便轻松实现
可扩展。
这是我在USENET上读过的最有用的信息。
我已经研究了你的答案，我现在明白了设置这个
的一种方法。我在下面放了一些简单的代码。
一件事：如果我们需要使用
base_types的arcoitrary数字怎么办？似乎没有''组合手段''（我已经学到了很多东西，这对麻省理工学院的在线MIT课程很重要。）
它'''可能很容易猜到我没有现实世界的编程
经验。
也许这样的问题在语言设计之外并不常见。
这里有证据证明我读了代码：
==================== =============
#include< stdio.h>
#include< stdlib.h>
#include< stddef.h>
#include< stdbool.h>
struct record
{
int value;
char * data;
};
typedef struct record basic_type;
/ ******************************* /
void map（const basic_type * src，basic_type * dst，void * ext_var，
basic_type（* trans_func）（basic_type *，void *），size_t arr_len）
{
for（int i = 0; i< arr_len; i ++）
{
dst [i] = trans_func（& src [i]，ext_var）;
}
}
size_t过滤器（const basic_type * src，basic_type * dst，void * ext_var，
_Bool（* pred_func）（basic_type * ，void *），size_t arr_len）
{
basic_type * node_in = src;
basic_type * node_out = dst;
size_t count = 0;
for（int i = 0; I< arr_len; i ++）
{
if（pred_func（src，ext_var））
{
* dst ++ = * src ++ ;
count ++;
}
其他src ++;
}
返回计数;
}
/ ******************************* ******************* ************** /
/ ******* *****转换功能**************************** /
/ ***** ********************************************* ***** ********* /
basic_type trans_one（basic_type * in，void * ext_var）
{
返回* in;
}
basic_type trans_two（basic_type * in，void * ext_var）
{
返回* in;
}
/ ********************* ***************************** **************** /
/ **************谓词函数***************************** **** /
/ ************************************ ************** **************** /
_Bool pred_one（basic_type * in， void * ext_var）
{
返回true;
}
_Bool pred_two（basic_type * in， void * ext_var）
{
返回false;
}
========= ===================================
[Thanks Dave Vandervies, that was the most useful piece of information
I''ve ever read on USENET.]
It''s still not possible to play with an arbritrary number of
base_types? It might be easy to set everything up to make it easily
extendable.
That was the most useful piece of information I''ve ever read on USENET.
I''ve studied your answer, and I now understand one way of setting this
up. I''ve chucked some simple code below.
One thing: What if we needed to play with an arbritrary number of
base_types? There seems to be no ''means of combination'' (which I have
learnt is important off of those online MIT lectures.)
It''s probably easy to guess that I''ve got zero real-world programming
experience.
Maybe problems like that aren''t so common outside of language design.
Here''s proof that I read the code:
=================================
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
struct record
{
int value;
char *data;
};
typedef struct record basic_type;
/*******************************/
void map(const basic_type *src, basic_type *dst, void *ext_var,
basic_type (*trans_func)(basic_type *, void *), size_t arr_len)
{
for (int i=0; i<arr_len; i++)
{
dst[i] = trans_func(&src[i], ext_var);
}
}
size_t filter(const basic_type *src, basic_type *dst, void *ext_var,
_Bool (*pred_func)(basic_type *, void *), size_t arr_len)
{
basic_type *node_in = src;
basic_type *node_out = dst;
size_t count = 0;
for (int i=0; i<arr_len; i++)
{
if (pred_func(src, ext_var))
{
*dst++ = *src++;
count++;
}
else src++;
}
return count;
}
/************************************************** **************/
/************Transformation functions****************************/
/************************************************** **************/
basic_type trans_one(basic_type *in, void *ext_var)
{
return *in;
}
basic_type trans_two(basic_type *in, void *ext_var)
{
return *in;
}
/************************************************** ****************/
/**************Predicate functions*********************************/
/************************************************** ****************/
_Bool pred_one(basic_type *in, void *ext_var)
{
return true;
}
_Bool pred_two(basic_type *in, void *ext_var)
{
return false;
}
============================================
在文章< 11 ********************** @ i42g2000cwa.googlegroups .com> ;,
ballpointpenthief< ba***************@yahoo.co.ukwrote：
In article <11**********************@i42g2000cwa.googlegroups .com>,
ballpointpenthief <ba***************@yahoo.co.ukwrote:
> [感谢Dave Vandervies，这是最多的有用的信息
我曾经在USENET上读过。]
>[Thanks Dave Vandervies, that was the most useful piece of information
I''ve ever read on USENET.]
只有一个结论可以从中得出：你有
There is only one conclusion that can be drawn from that: You have
obviously not read anything by Chris Torek.
>我已经研究了你的答案，我现在明白了一种方法设置这个
。我在下面放了一些简单的代码。
>I''ve studied your answer, and I now understand one way of setting this
up. I''ve chucked some simple code below.
....我对它有一些评论，我会投入内联。
....and I have a few comments on it that I''ll throw in inline.
>一件事：如果我们需要使用arcoitrary数量的
base_types怎么办？
>One thing: What if we needed to play with an arbritrary number of
base_types?
那么你必须要聪明一点。
处理这种情况的明显方法是使用泛型（比如C ++模板）
或动态类型（如Scheme或Smalltalk）。不幸的是，
C没有这些，并且试图重新创建它们通常是（但并不总是）b $ b错误的解决方案。
（C的一大好处是你可以*构建你想要使用的任何高级别的
抽象[1]; C的一大问题是
你*需要*来构建你想要使用的任何高级抽象。）
一种稍微不那么明显的方式，但是可能更通用的一种方式/>
一般来说更适合C，就是给类型不可知的代码一个空的
指针指向你的数据以及数据的大小，并让
回调函数（知道他们正在使用的是什么）将
void指针转换回指向相应数据类型的指针。
qsort和bsearch使用这个; qsort的原型是
--------
void qsort（void * base，size_t nmemb，size_t size，
int（* compar）（const void *，const void *））;
--------
，实现将执行与此相同的操作：
--------
void qsort（void * base，size_t nmemb，size_t size，
int（* compar） （const void *，const void *））
{
/ *获取一个我们可以算术的指针* /
char * base_c =基础;
/*...do排序东西，包括...... * /
if（（* compar）（base_c + i * size ，base_c + j * size）0）
__swap_memory（base_c + i * size，base_c + j * size，size）;
}
--------
（所以只需要告诉类型不可知代码有多大的数据
元素所以它可以抛出它们，并允许来电者提供的代码
用它们做其他所有事情。）
一个完全类型不可知的地图，这种类型的界面看起来像什么
喜欢这个s：
--------
void map（const void * vfrom，size_t from_size，void * vto，size_t to_size，
size_t nelem，
void（* trans_func）（const void * from，void * to，void * cookie），
void * cookie）
{
const char * from = vfrom;
unsigned char * to = vto;
size_t i;
for（i = 0; i< nelem; i ++）
{
trans_func（从+ i * from_size到+ i * to_size， cookie）;
}
}
--------
和变换函数会看起来像这样：
--------
void frob（const void * vfrom，void * to，void * vcookie）
{
const type1 * from = vfrom;
type2 * to = vto;
cookie_type * cookie = vcookie;
/ *现在用*来自（和*可选* cookie）和
将结果输入*到
* /
}
--------
请注意，以这种方式做事你仍然需要一个不同的变换
$对于你使用的每种类型都有b $ b函数，即使你正在对它们进行相同的操作
- 添加-17到int函数可能不会给你
如果你要求地图在你的双打数组上调用它你想要的结果。
另请注意，这不会对你回调的任何类型检查
给它。如果你小心并且知道你在做什么，那可能不是一个主要的缺点，但它确实意味着如果你弄错了编译器
会很乐意生成代码，这些代码会无声地破坏您的数据（或者，如果你很幸运，可以使你的程序崩溃，而不是抱怨你已经损坏了你的程序） b弄错了。 （当然，如果你不小心或者不知道你在做什么，你可能不应该尝试编程
计算机，但似乎并没有阻止很多人。）
Then you have to be a bit more clever.
The obvious ways to handle that are to use generics (like C++ templates)
or to have dynamic typing (like in Scheme or Smalltalk). Unfortunately,
C has neither of those, and trying to re-create them is usually (but
not always) the wrong solution.
(One of the big benefits of C is that you *can* build any high-level
abstraction you want to use[1]; one of the big problems of C is that
you *need* to build any high-level abstraction you want to use.)
A slightly less obvious way, but one that''s probably more general and
better-suited to C in general, is to give the type-agnostic code a void
pointer that points at your data along with the size of the data, and let
the callback functions (which know what they''re working with) convert the
void pointer they get back to a pointer to the appropriate type of data.
qsort and bsearch use this; the prototype for qsort is
--------
void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(const void *, const void *));
--------
and the implementation will do something equivalent to this:
--------
void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(const void *, const void *))
{
/*Get a pointer we can do arithmetic on*/
char *base_c=base;
/*...do sort stuff, including...*/
if((*compar)(base_c+i*size,base_c+j*size) 0)
__swap_memory(base_c+i*size,base_c+j*size,size);
}
--------
(so the type-agnostic code only needs to be told how big the data
elements are so it can throw them around, and lets caller-provided code
do everything else with them).
A fully type-agnostic map with this type of interface would look something
like this:
--------
void map(const void *vfrom,size_t from_size,void *vto,size_t to_size,
size_t nelem,
void (*trans_func)(const void *from,void *to,void *cookie),
void *cookie)
{
const char *from=vfrom;
unsigned char *to=vto;
size_t i;
for(i=0;i<nelem;i++)
{
trans_func(from+i*from_size,to+i*to_size,cookie);
}
}
--------
and the transform function would look like this:
--------
void frob(const void *vfrom,void *to,void *vcookie)
{
const type1 *from=vfrom;
type2 *to=vto;
cookie_type *cookie=vcookie;
/*Now do stuff with *from (and optionally *cookie) and
stuff the results into *to
*/
}
--------
Note that to do things this way you''d still need a different transform
function for each type you use, even if you''re doing the same operations
on them - an add-seventeen-to-int function would probably not give you
the results you want if you ask map to invoke it on your array of doubles.
Note also that this doesn''t do any type-checking on the callback you
give it. If you''re careful and know what you''re doing, that''s probably
not a major lack, but it does mean that if you get it wrong the compiler
will happily generate code that will silently corrupt your data (or,
if you''re lucky, crash your program) instead of complaining that you''ve
gotten something wrong. (Of course, if you''re not careful or don''t
know what you''re doing, you probably shouldn''t be trying to program a
computer at all, but that doesn''t seem to stop a lot of people.)
似乎没有''组合手段''（其中我已经了解了那些在线MIT讲座的重要性。）
There seems to be no ''means of combination'' (which I have
learnt is important off of those online MIT lectures.)
我不太确定你的意思是组合方式 。
如果你的意思是能够使用不同的聚合类型，那么就像你用不同的基本类型一样使用不同的聚合类型 - 或者通过
为每种类型编写一个版本，或者通过应用一些聪明来
避免必须完成所有工作（通过获取代码生成器来
为你完成或完全避免它。）
如果你的意思是编写功能，你可以用假装闭合来实现这一点
同样的方式你会用真正的闭包来做;相当于：
--------
（定义（反过滤器lis pred）
（过滤器lis（ lambda（x）（不是（pred x）））））
--------
会是这样的：
--------
struct not_cookie
{
void * orig_cookie;
_Bool （* orig_pred）（basic_type * in，void * cookie）;
};
静态_Bool not（basic_type * in，void * vcookie）
{
struct not_cookie * cookie = vcookie;
return！（*（cookie-> orig_pred））（in，cookie-> orig_cookie ）;
}
size_t anti_filter（const basic_type * src，basic_type * dst，void * ext_var，
_Bool（* pred_func）（basic_type *，void *），size_t arr_len）
{
struct not_cookie nc;
nc.orig_cookie = ext_var;
nc.orig_pred = pred_func;
返回过滤器（src，dst，& nc，not，arr_len）;
}
--------
（以及这两个例子的相对长度这就是为什么有些人会试图告诉你需要闭包和匿名函数才能有效地使用高阶函数.b
$ b使用高阶函数。他们错了，但他们确实有一点值得注意的。
I''m not quite sure what you mean by "means of combination".
If you mean being able to use different aggregate types, you do that
the same way as you''d do it with different basic types - either by
writing one version for every type or by applying some cleverness to
avoid having to do all that work (either by getting a code generator to
do it for you or by avoiding it altogether).
If you mean composing functions, you can do that with fake-closures the
same way you''d do it with real closures; the equivalent of this:
--------
(define (anti-filter lis pred)
(filter lis (lambda (x) (not (pred x)))))
--------
would be something like this:
--------
struct not_cookie
{
void *orig_cookie;
_Bool (*orig_pred)(basic_type *in,void *cookie);
};
static _Bool not(basic_type *in, void *vcookie)
{
struct not_cookie *cookie=vcookie;
return !(*(cookie->orig_pred))(in,cookie->orig_cookie);
}
size_t anti_filter(const basic_type *src, basic_type *dst, void *ext_var,
_Bool (*pred_func)(basic_type *, void *), size_t arr_len)
{
struct not_cookie nc;
nc.orig_cookie=ext_var;
nc.orig_pred=pred_func;
return filter(src,dst,&nc,not,arr_len);
}
--------
(and the relative length of these two examples is why some people will
try to tell you you need closures and anonymous functions to usefully
use higher-order functions. They''re wrong, but they do have a point
that''s worth paying attention to.)
>可能很容易猜到我没有真实的编程体验。
>It''s probably easy to guess that I''ve got zero real-world programming
experience.
由于零实际编程经验，你的代码是相当的
好。我假设你至少有一些非现实世界的经历吗？
（差异并不总是像很多人一样大）
尝试告诉你他们是。）
For having zero real-world programming experience, your code is Rather
Good. I assume you have at least some non-real-world experience?
(The differences aren''t always as big as big as a lot of people will
try to tell you they are.)
>这里有证据证明我读了代码：
>Here''s proof that I read the code:
[大多数代码被剪掉，只留下我评论的部分]
[most code snipped, leaving only the parts I have comments on]
> #include< stdbool.h>
>#include <stdbool.h>
请注意< stdbool.hand _Bool是C99中的新功能。值得保留在
介意C99实现在野外仍然相当罕见，因此对于
最大可移植性，您可能仍然希望避免C99isms。
（对于一个已经存在七年的标准
来说这是不是可耻的事态是我试图避免的讨论
进入，但实际后果不受你的
位置的影响。）
如果你使用int作为具有布尔意义的值，大多数C程序员将b / b
搞清楚那就是你的意思，并且他们将会b / b
也可以使用他们的C90编译器（通常是
被认为是一件好事。
Note that <stdbool.hand _Bool are new in C99. It''s worth keeping in
mind that C99 implementations are still rather rare in the wild, so for
maximal portability you probably still want to avoid C99isms.
(Whether or not this is a disgraceful state of affairs for a standard
that''s been around for seven years is a discussion that I try to avoid
getting into, but the pragmatic consequences aren''t affected by your
position on that.)
If you use int for values with boolean meaning, most C programmers will
have no trouble figuring out that that''s what you meant, and they''ll
also be able to compile it with their C90 compilers (which is generaly
considered a Good Thing).
> void map（const basic_type * src，basic_type * dst，void * ext_var，
basic_type（* trans_func）（basic_type *，void *），size_t arr_len）
>void map(const basic_type *src, basic_type *dst, void *ext_var,
basic_type (*trans_func)(basic_type *, void *), size_t arr_len)
没有真的有任何理由给回调函数一个指针来指示它的输入而不仅仅是数据对象（除非你的basic_data类型
很大，在这种情况下你可能会更好只是传递一个指针，
然后你可能想要为dst做一些类似的事情。）
如果你传递指针，你应该把它变成const。 br />
所以trans_func的类型可能在这里错了，应该是
basic_type（* trans_func）（basic_type，void *）
或
basic_type（* trans_func）（const basic_type *，void *）
取决于你是否真的想要传递指针。
There''s not really any reason to give the callback function a pointer to
its input instead of just the data object (unless your basic_data type
is big, in which case you might be better off just passing a pointer,
but then you probably want to do something comparable for dst).
If you are passing the pointer, you should probably make it const.
So the type of trans_func is probably wrong here, and should either be
basic_type (*trans_func)(basic_type,void *)
or
basic_type (*trans_func)(const basic_type *,void *)
depending on whether you really want to pass a pointer or not.
> {
for（int i = 0; I< arr_len; i ++）
{
dst [i] = trans_func（& src [i]，ext_var）;
}
}
>{
for (int i=0; i<arr_len; i++)
{
dst[i] = trans_func(&src[i], ext_var);
}
}
并非所有的新闻阅读器都能很好地使用标签，而且并非所有的新闻阅读器都可以使用相同的宽度处理它们，所以如果你想要你的代码内衬
很好（特别是除了开头的缩进之外的任何东西
行的
）你可能最好将它们转换成空格，然后再发布
。
Not all newsreaders play nicely with tabs, and not all the ones that do
handle them sensibly use the same width, so if you want your code lined
up nicely (especially for anything other than indents at the beginning
of the line) you''re probably better off converting them to spaces before
you post.
> size_t过滤器（const basic_type * src，basic_type * dst，void * ext_var，
_Bool（* pred_func）（basic_type *，void * ），size_t arr_len）
{
basic_type * node_in = src;
basic_type * node_out = dst;
>size_t filter(const basic_type *src, basic_type *dst, void *ext_var,
_Bool (*pred_func)(basic_type *, void *), size_t arr_len)
{
basic_type *node_in = src;
basic_type *node_out = dst;
因为你没有使用这些东西，所以没有太多意义
让它们保持不变。 （调用者可能需要原始值，
但它有自己的副本。）
Since you''re not using these for anything, there''s not much point
keeping them around. (The caller probably needs the original values,
but it has its own copy.)
> size_t count = 0;
for（int i = 0; i< arr_len; i ++）
{
if（pred_func（src，ext_var））
{
* dst ++ = * src ++;
count ++;
}
其他src ++;
}
返回计数;
}
> size_t count = 0;
for (int i=0; i<arr_len; i++)
{
if (pred_func(src, ext_var))
{
*dst++ = *src++;
count++;
}
else src++;
}
return count;
}
对我来说，做数组索引而不是走路时，我觉得更清楚了。
指针通过。数组索引使您可以保持输出计数
和同一位置的dst-position，以及迭代次数
和src-position。
（这是品味和风格的问题;一个适度聪明的优化器
应该产生相同的输出。一个C ++程序员可能会发现你的b $ b版本也更容易理解，因为它更多
与C ++迭代器习语紧密匹配。）
dave
[1]嗯，有些它们很难以最终减少不会因为没有而感到痛苦。 （有时当你感觉受到虐待时，请尝试实现完全通用的协同程序，而不是使用
来调用特定于实现的知识。但即便如此*也可以*
$ b如果你不介意明确管理你的电话堆栈框架，你可以完成
$ b（如果你做得对，你甚至可以获得一流的延续
of这笔交易。）
-
Dave Vandervies dj ****** @ csclub.uwaterloo.ca
有两种程序结构：我可以轻松处理的那些
in my不使用纸张的头，以及那些无论如何都不适合任何纸张的纸张。 --Christian Bau in comp.lang.c
It seems clearer to me to do this as array indexing instead of walking
the pointers through. Array indexing lets you keep the output count
and the dst-position in the same place, and also the iteration count
and the src-position.
(That''s a matter of taste and style, though; a moderately clever optimizer
should produce equivalent output either way. A C++ programmer would
probably find your version easier to understand, too, since it more
closely matches the C++ iterator idioms.)
dave
[1] Well, some of them are hard enough that it ends up being less
painful to just do without. (Sometime when you''re feeling
masochistic, try implementing fully general coroutines without
invoking implementation-specific knowledge. But even that *can*
be done if you don''t mind explicitly managing your call-stack frames
(and if you do it right you even get first-class continuations out
of the deal).)
--
Dave Vandervies dj******@csclub.uwaterloo.ca
There are two kinds of program structures: Those that I can easily handle
in my head without the use of paper, and those that wouldn''t fit on any
kind of paper anyway. --Christian Bau in comp.lang.c
这篇关于地图，过滤器和累加器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
