Point-free function to add 2 elements to the list / double application of (:) list data constructor and (.)

huangapple go评论78阅读模式
英文:

Point-free function to add 2 elements to the list / double application of (:) list data constructor and (.)

问题

我正在努力正确定义函数的无点版本,该函数将两个元素添加到列表中。

很容易想出一些直接的简单实现:

addTwoElems :: a -> a -> [a] -> [a]

addTwoElems x y xs = x : y : xs
addTwoElems x y    = (++) [x, y]
addTwoElems        = (.) `on` (:)  -- 无点版本,但使用了额外的函数

但是,如何使用两个列表数据构造函数 (:) 进行无点组合 (.) 呢?

请不仅展示正确的函数实现,还请解释每个步骤和逻辑,说明如何得出正确的版本。

英文:

I am struggling to define correctly the point-free version of the function, which adds 2 elements to the list.

It is easy to come up with a number of straightforward trivial implmentations:

addTwoElems :: a -> a -> [a] -> [a]

addTwoElems x y xs = x : y : xs
addTwoElems x y    = (++) [x, y]
addTwoElems        = (.) `on` (:)   point free but with additional function

But how would a point-free composition (.) of the two list data constructors (:) look like?

Please not just show the correct function implementation, but please with explanations of the steps and logic behind how to come to the right version.

答案1

得分: 6

根据评论,以下是仅使用 .: 的逐步推导过程:

addTwoElems x y xs = x : y : xs
-- 将第一个 : 重写为前缀函数
addTwoElems x y xs = (:) x (y : xs)
-- 将第二个 : 重写为前缀函数
addTwoElems x y xs = (:) x ((:) y xs)
-- 使用函数组合将 xs 从括号中提取出来
addTwoElems x y xs = ((:) x . (:) y) xs
-- 使用 eta 缩减来消除 xs
addTwoElems x y = (:) x . (:) y
-- 将 . 重写为前缀函数
addTwoElems x y = (.) ((:) x) ((:) y)
-- 使用函数组合将 y 从括号中提取出来
addTwoElems x y = ((.) ((:) x) . (:)) y
-- 使用 eta 缩减来消除 y
addTwoElems x = (.) ((:) x) . (:)
-- 将第二个 . 重写为操作符部分,使得表达式中包含 x 的部分位于最后
addTwoElems x = (. (:)) ((.) ((:) x))
-- 使用函数组合将 x 从内部括号中提取出来
addTwoElems x = (. (:)) (((.) . (:)) x)
-- 使用函数组合将 x 从外部括号中提取出来
addTwoElems x = ((. (:)) . (.) . (:)) x
-- 使用 eta 缩减来消除 x
addTwoElems = (. (:)) . (.) . (:)

以上是给定代码的逐步推导过程。

英文:

Per the comments, a step-by-step derivation that only uses . and ::

addTwoElems x y xs = x : y : xs
-- rewrite the first : as a prefix function
addTwoElems x y xs = (:) x (y : xs)
-- rewrite the second : as a prefix function
addTwoElems x y xs = (:) x ((:) y xs)
-- use function composition to get xs out of the parentheses
addTwoElems x y xs = ((:) x . (:) y) xs
-- eta-reduce to get rid of xs
addTwoElems x y = (:) x . (:) y
-- rewrite the . as a prefix function
addTwoElems x y = (.) ((:) x) ((:) y)
-- use function composition to get y out of the parentheses
addTwoElems x y = ((.) ((:) x) . (:)) y
-- eta-reduce to get rid of y
addTwoElems x = (.) ((:) x) . (:)
-- rewrite the second . as an operator section, so that the part of the expression with x is last
addTwoElems x = (. (:)) ((.) ((:) x))
-- use function composition to get x out of the inner parentheses
addTwoElems x = (. (:)) (((.) . (:)) x)
-- use function composition to get x out of the outer parentheses
addTwoElems x = ((. (:)) . (.) . (:)) x
-- eta-reduce to get rid of x
addTwoElems = (. (:)) . (.) . (:)

huangapple
  • 本文由 发表于 2023年8月8日 21:50:18
  • 转载请务必保留本文链接:https://go.coder-hub.com/76860201.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定