Какой самый эффективный способ реализовать J1 в Haskell? - PullRequest
5 голосов
/ 06 марта 2011

В Haskell есть две функции, которые позволяют выполнить операцию со списком элементов, чтобы свести ее к одному значению. (Конечно, их больше двух, но это те, которые меня интересуют.) Это foldl1 и foldr1. Если выполняемая операция коммутативная (например, сложение), не имеет значения, какую из них вы используете. Результат будет таким же. Однако, если операция является , а не коммутативной (например, вычитание), тогда эти два результата дают очень разные результаты. Например:

foldr1 (-) [1..9]
foldl1 (-) [1..9]

Ответ на первый вопрос - 5, а на второй -43. Эквивалент J foldr1 представляет собой наречие вставки, /, например,

-/ 1+i.9

что эквивалентно foldr1 (-) [1..9]. Я хочу создать наречие в J, которое работает как наречие вставки, но сгибается влево, а не вправо. Лучшее, что я мог придумать, это следующее:

foldl =: 1 : 'u~/@|.'

Таким образом, можно сказать:

- foldl 1+i.9

и получите -43 в качестве ответа, что и ожидается от левой складки.

Есть ли лучший способ сделать это в J? По некоторым причинам обращение аргумента y не кажется мне эффективным. Возможно, есть способ сделать это, не прибегая к этому.

Ответы [ 2 ]

3 голосов
/ 09 марта 2011

Я не думаю, что есть лучший способ сложить влево, чем вы описываете:

(v~) / (|. list)

Это очень естественный способ, почти "буквальная" реализация определения. Стоимость обращения к списку очень мала (IMO).

Другой очевидный способ реализации левой складки - установить

new_list = (first v second) v rest

например:

foldl_once =: 1 :'(u / 0 1 { y), (2}. y)'
foldl =: 1 :'(u foldl_once)^:(<:#y) y'

так:

- foldl >:i.9
_43

но ваш путь выполняет намного лучше, чем в пространстве и времени.

1 голос
/ 08 марта 2011
   ($:@}:-{:)^:(1<#) 1+i.9
_43

Понятия не имею, эффективен ли он (или менее).

...