取回原始x:xs

Question

我想在Haskell中创建一个函数,如下所示:

encode :: [(Char,Char)] - > String - > String

我有一个名为"table"的"字典"函数,它创建了一对对列表:

table :: Int -> [Char] -> [(Char, Char)]
table __ [] = []
table n l   = zip l (drop n (cycle l))

encode函数按字符对字符串进行编码.到目前为止它看起来像这样:

encode (x:xs) (n:ns)
| length(n:ns) > 1 && (fst x) == n  = [snd x] ++ (encode (x:xs) ns)
| length(xs) > 1 && (fst x) /= n    = encode xs (n:ns)
| length(ns) > 0 && length(xs) == 0 = encode (x:xs) ns

对于测试,encode table2 "SOS"它只给我"U"但它需要是"UQU".table2是一个常量:table2 = table 2 (['a'..'z'] ++ ['A'..'Z'] ++ ['.', '!', '?', ' '])

我的问题是:我怎样才能找回(x:xs)的原始列表？我想我只得到一个"U",因为我总是用xs返回它并切断第一对,但我需要每个角色的整个原始(x:xs).

常数函数返回:图片

Answer 1

您的函数问题是当您搜索关联列表时,您会在开头丢弃值.您只需要保留对该列表的引用.你可以执行转换

encode l n0 = encode' l n0 where 
  encode' (x:xs) (n:ns) 
    | ... = snd x : encode (x:xs) ns0

但是你可以认识到更高级别的抽象会使这个问题变得更加简单.

假设您有一个Table可以编码一个的抽象类型Char.编码可能会失败(字符可能没有关联),因此它返回Maybe Char:

type Table = ...
encode1 :: Table -> Char -> Maybe Char

然后对整个字符串进行编码,只需使用相同的表对每个字符进行编码 - 如果有任何返回Nothing,则返回Nothing.字符串是一个列表,您需要将一个带有效果的函数应用于该列表的每个元素 - 这正是mapM:

encode :: Table -> [Char] -> Maybe Char
encode t = mapM (encode1 t)

现在问题是如何定义Table.由于它表示关联映射,为什么不使用关联映射数据类型 - Data.Map.

import qualified Data.Map as M

type Table = M.Map Char Char 

encode1 :: Table -> Char -> Maybe Char 
encode1 = flip M.lookup 

table :: Int -> [Char] -> [(Char, Char)]
table _ [] = []
table n l   = zip l (drop n (cycle l))

table' :: Int -> [Char] -> Table
table' n l = M.fromList (table n l) 

现在:

> encode (table 2 (['a'..'z'] ++ ['A'..'Z'] ++ ['.', '!', '?', ' '])) "SOS"
Just "UQU"