我如何計算列表中每個字符串的位置與每個字符串的發生次數？

我需要做這樣的事情：我如何計算列表中每個字符串的位置與每個字符串的發生次數？

func ["a","bb","c","aa","bb","c"] ⟼ 
    [("a",[0]), ("bb",[1,4]),("c",[2,5]),("aa",3)]

使用此項功能：

func :: [String] -> [(String, [Int])]

我的想法是這樣的：

func :: [String] -> [(String, [Int])] 
func (xs) = func1 (reverse xs) 
    where 
    func1 [] = [] 
    func1 (x:xs) 
     | notElem x xs = func1 (xs) ++ [(x, [0])] 
     | otherwise = func1 (xs)

0只是一個佔位符，怎麼能我把這些指數放在那個位置？

來源

2016-03-10 KnightOfArcadia

如果您不限制使用列表作爲結果數據類型我建議您切換到'Data.Map' - 然後'insertWith'函數非常方便 - 特別是 - 結合在@Chad-Gilbert推薦的'zip'上的'fold' – epsilonhalbe

zip [0..] xs會給你一個元組列表，其中第一個項目是從零開始的索引，第二個項目是該索引處的字符串。

來源

2016-03-10 00:20:29

爲了獲得索引，您的幫助函數只需要一個額外的參數，您可以將0初始化並在每次遞歸調用時遞增。雖然您可能需要更改，當您撥打reverse以獲得正確順序的索引時！

您必須考慮的第二部分是管理您創建的輸出對列表的最佳方法。像這樣的對的列表有時稱爲「關聯列表」，並且Prelude中有一個lookup函數，您可以使用該函數獲取與此類結構中的鍵相關聯的值。您可能會研究該函數，並編寫一個update幫助器，以便更新現有密鑰的值。

然而，還有另一種通用的方法來解決問題，@Chad Gilbert在他的回答中暗示。不是直接使用遞歸，而是通常可以將解決方案定義爲轉換的組合並將問題結構中的操作組合起來。這種形式的解決方案通常結合了映射，過濾，壓縮和摺疊。我會推薦使用這兩種解決方案來練習。

來源

2016-03-10 00:52:16

我不知道這是否會幫助，但這個是我做了什麼來解決這個問題

zipPos :: [String] -> [(String, Int)] 
zipPos xs = zip xs [0..] 

singleHead :: ([String], [Int]) -> (String, [Int]) 
singleHead (x,y) = (head x, y) 

filterFstTuple :: (String -> String -> Bool) -> [(String, Int)] -> [(String, Int)] 
filterFstTuple _ [] = [] 
filterFstTuple con [email protected](x:_) = filter (con (fst x).fst) xss 

getPos :: [(String, Int)] -> [(String, [Int])] 
getPos [] = [] 
getPos xss = singleHead (unzip (filterFstTuple (==) xss)) : getPos (filterFstTuple (/=) xss) 

main :: IO() 
main = print . getPos $ zipPos ["a", "b", "c", "c", "d", "a"]

來源

2016-03-10 02:41:25

這是非常不清楚的，並且使用'head'被廣泛地勸阻。 – dfeuer

它已經假定你在元組中有一個值，並且加入的值是相同的，那麼爲什麼遍歷只要獲得頭就可以摺疊相同的值。那麼這就是我使用的邏輯，我不知道別人會怎麼做。但是解釋代碼，我想我會編輯帖子 –

有些情況下，爲了提高效率，程序會跟蹤一些關於結構大小/形狀的冗餘信息。在這種情況下，效率可能要求程序信任冗餘信息來證明其他部分操作的合理性。我目前想到的例子是'Data.Sequence'的最新版本中'zipWith'的實現，但我知道我見過其他人。然而，在你的情況下，沒有特別的需要依賴'head'。 – dfeuer

這裏有一個如何使用Data.Map來解決這樣的一個例子。（我不知道是否有更好的方法來處理zipWith）

import Data.Map (Map) 
import qualified Data.Map as Map 

func :: [String] -> [(String, [Int])] 
func xs = Map.toList .       -- [("a", [0]), ("bb", [1,4]), ...] 
      (Map.map reverse) .     -- fromList [("a", [0]), ("bb", [1,4]), ...] 
      (Map.fromListWith (++)) $    -- fromList [("a", [0]), ("bb", [4,1]), ...] 
      zipWith (\c i -> (c, [i])) xs [0..] -- [("a", [0]), ("bb", [1]), ...]

這始於元組配對每串其在輸入位置的單清單列表，然後建立一個地圖，每個鍵被映射到一個累積的位置列表。累積的位置以相反的順序建立，其中Map.map reverse修復，然後從地圖中提取所需的列表。

這是一個優化的版本，由dfeuer提供。

func = map (\(a,b) -> (a, reverse b)) . 
     Map.toList . 
     Map.fromListWith (++) . 
     zipWith (\i c -> (c, [i])) [0..]

來源

2016-03-10 18:28:56 chepner

我如何計算列表中每個字符串的位置與每個字符串的發生次數？

回答

相關問題