除算を使わずに現在のインデックスを除いた要素の積にリストをマッピングする

Question

私はHaskellでいくつかの練習をしていますが、これは現在私がhttps://leetcode.com/problems/product-of-array-except-self/で作業しているものです。

n> 1、numsのn個の整数の配列を指定すると、output [i]がnums [i]以外のnumのすべての要素の積と等しくなる配列出力が返されます。

分割せずにO（n）で解いてください。

たとえば、[1,2,3,4]を指定すると、[24,12,8,6]を返します。

私は部門でかなり簡単にそれを行うことができました：

import Data.List (foldl1') 

productOfArray :: [Int] -> [Int] 
productOfArray xs = f <$> xs 
    where p = foldl1' (*) 
     f = div (p xs) 

しかし、私は分裂を行わず、それにアプローチする方法が非常にわかりません。命令型アプローチは、現在のインデックスの左側にあるすべての数字と現在のインデックスの右側にあるすべての数字との積にマップされますが、ハスケルではそれをどのように概念化するかについてはあまりよく分かりません。

Answer 1

tailsとinits関数を使用すると、N番目以降のすべての要素を返すことができます。

> tails [1,2,3,4] 
[[1,2,3,4], [2,3,4], [3,4], [4]] 

最初の値を削除した場合、これは欠落した要素の後に掛けなければならない値になります。欠番

> heads [1,2,3,4] 
[[], [1], [1,2], [1,2,3], [1,2,3,4]] 

は最後に、最後の乗算を行うために、製品の機能やzipwithを使用する前に

> tail $ tails [1,2,3,4] 
[[2,3,4], [3,4], [4]] 

initsは値を返します。非最適化アプローチについて

zipWith (*) (map product $ inits [1,2,3,4]) (map product $ tail $ tails [1,2,3,4])