[net.lang] FP puzzle answer

dfz (02/02/83)

Well, I was inundated with exactly zero replies to my "FP puzzle" of a few
weeks ago.  But here's the answer anyway:

Assume the following notation:

	apply-to-all:			@
	composition:			.
	condition:			-> ;
	construction:			[]
	left insert			<
	right insert:			>
	constant function x:		$x
	selector function x:		?x
	tail of a list			tl
	head of a list			hd
	arithmetic equality		eq
	append left			apl
	append right			apr

Then Backus' null function is:

	count = >+.@$1		{count the elements of a list}
	null = eq.[count,$0]	{Backus' null function}

By the way, the above definition would not work if not for Backus' extension
to the definition of "insert right".  Why?

Distribute from left is:

	cnt1 = eq.[count,$1]		{list contains one element?}
	d1l = [?1,?1.?2]		{distr. from left for 1-elt list}

	{generalized distribute from left}
	distl = null.?2 -> ?2 ; cnt1.?2 -> [d1l] ; apl.[d1l,distl.[?1,tl.?2]]

Distribute from right is:

	last = eq.[count,$1] -> ?1 ; ?2.<id	{last element of a list}
	d1r = [last.?1,?2]		{distr. from right for 1-elt list}

	{generalized distribute from right}
	distr = null.?1 -> ?1 ; cnt1.?1 -> [d1r] ; apr.[distr.[hd.?1,?2],d1r]

These are only representatives of a large set of reasonable answers to the
puzzle.  If you can think of more efficient or elegant answers, please send
them in.
				Dave Ziffer
				..!decvax!ihnss!iwlc7!dfz