Haskell将元素添加到现有列表中

Question

我想写的功能是让用户输入他们的名字和他们想成为粉丝的电影.

这是我正在使用的当前代码:

type Title = String
type Actor = String
type Cast = [Actor]
type Year = Int
type Fan = String
type Fans = [Fan]
type Period = (Year, Year)
type Film = (Title, Cast, Year, Fans)
type Database = [Film]

testDatabase :: Database
testDatabase = [("Casino Royale", ["Daniel Craig", "Eva Green", "Judi Dench"], 2006, ["Garry", "Dave", "Zoe", "Kevin", "Emma"]),
    ("Cowboys & Aliens", ["Harrison Ford", "Daniel Craig", "Olivia Wilde"], 2011, ["Bill", "Jo", "Garry", "Kevin", "Olga", "Liz"]),     
        ("Catch Me If You Can", ["Leonardo DiCaprio", "Tom Hanks"], 2002, ["Zoe", "Heidi", "Jo", "Emma", "Liz", "Sam", "Olga", "Kevin", "Tim"]),           
            ("Mamma Mia!", ["Meryl Streep", "Pierce Brosnan"], 2008, ["Kevin", "Jo", "Liz", "Amy", "Sam", "Zoe"])]

使用此作为类型:

becomeFan :: String -> String -> [Film] -> [Film]

我是否能够执行此任务,例如,如果用户"Bob"想成为电影"妈妈咪呀!"的粉丝.然后数据库将更新粉丝列表:

["Kevin", "Jo", "Liz", "Amy", "Sam", "Zoe"]

至:

["Bob", "Kevin", "Jo", "Liz", "Amy", "Sam", "Zoe"]

在此先感谢所有提供的答案!!

Answer 1

这是一个很好的例子,因为创建一个像你这样Endo的函数是一种在无状态语言中处理"状态"的好方法.让我们潜入.a -> a[Film] -> [Film]

因此,目标是创建一个像becomeFan "Joseph" "7 1/2" :: [Film] -> [Film]"电影数据库更新功能"的功能.要执行此更新,您需要修改电影数据库以更新"7 1/2"要包含的电影的粉丝列表"Joseph".我们假设每个用户的名称是全局唯一的并且多次写入此函数.

我们现在假设,如果电影不在我们的数据库中,那么becomeFan就不会做任何事情,并且数据库不包含重复项.

首先,我们有直接递归版本.

becomeFan _ _ [] = [] -- empty film database
becomeFan name film (f@(title, cast, year, fans) : fs)
  | film == title = (title, cast, year, name:fans) : fs
  | otherwise     = f : becomeFan name film fs

这将只是迭代数据库中的电影列表,如果flim标题与我们正在尝试编辑的标题匹配,则进行更新.请注意@-syntax,它允许我们拍摄我们正在"整体"检查的电影并仍然解构它.

这种方法面临的挑战无数,但它非常复杂!我们有许多基本假设与我们实施的方式相关联,这些假设becomeFan可能与我们编写的其他函数一起被取消.幸运的是,Haskell 非常善于解决这类问题.

第一步是介绍一些更强大的数据类型.

我们要做的是消除一些类型的同义词并引入一些更强大的容器类型,特别是Set它们的行为类似于数学集,Map并且类似于字典或散列.

import qualified Data.Set as Set
import qualified Data.Map as Map

我们还使用"记录"类型Film.记录与("功能上等同于")元组是同构的,但是具有对文档有用的命名字段,并且让我们使用较少的类型同义词.

type Name = String
type Year = Int
data Film = Film { title :: Title, cast :: Set Name, year :: Year, fans :: Set Name)

通过使用a Map Title Film来表示我们的数据库,我们也可以保证电影的独特性(Map使得键Title或者是零或一个Films - 我们不能有多个匹配).这里的缺点是,我们可能不同步的Title在Database用钥匙Title在Film类型本身.

type Database = Map Title Film

那么我们如何becomeFan在这个新系统中重写呢？

becomeFan name title = 
  Map.alter update title where
    update Nothing  = Nothing -- that title was not in our database
    update (Just f) = Just (f { fans = Set.insert name (fans f) })

现在我们主要依靠Map.alter :: (Maybe v -> Maybe v) -> k -> Map k v -> Map k v并Set.insert :: a -> Set a -> Set a完成繁重的工作并保持各种独特性限制.请注意,第一个参数Map.alter是一个函数Maybe v -> Maybe v,它允许我们处理丢失的电影(如果是输入Nothing)并决定从数据库中删除一部电影(如果我们返回Nothing).

值得注意的是,我们的内部函数update :: Maybe Film -> Maybe Film可以更容易编写,fmap (\f = f { fans = Set.insert name (fans f) })以便将"纯粹的"更新步骤提升到Maybe原来的状态Functor.

我们可以做得更好吗？当然,但这里让人感到困惑.在大多数情况下,之前的答案可能是您最好的选择.但是,让我们为了好玩而努力.

我们可以使用镜头从Control.Lens使我们访问到Map,Set和Film更容易.

为此,我们将导入模块

import Control.Lens

并重写Film类型,以便库可以使用宏自动生成镜头.

data Film = Film { _title :: Title, _cast :: Set Name, _year :: Year, _fans :: Set Name }
$(makeLenses ''Film)

我们所要做的就是在每个记录字段名称前面添加一个下划线,并Control.Lens.makeLenses以原始名称自动生成我们的镜头.因此,在那一行之后,我们就拥有title :: Lens' Film Title了我们想要的功能.

然后我们可以使用Map的At实例来创建我们的改变函数,就像以前一样,但是写成一串镜头操作

becomeFan name film = over (at film) (fmap . over fans . Set.insert $ name)

其中over (at film)概括和替换Map.alter并(fmap . over fans . Set.insert $ name)替换我们update之前定义的内部函数.

我们甚至可以构建一个功能强大的二传镜,直接看到某个粉丝列表中某个粉丝的存在Film.

isFan :: Name -> String -> Setter' Database Bool
isFan name film = at film . mapped . fans . contains name

这些方法起初相当令人讨厌,并且具有非常奇怪(但完全可检查)的类型,但是一旦你习惯于在那个抽象层次上工作它们就会变得非常好.它"读起来像英语",感觉就像XPath的好部分.

becomeFan name film = isFan name film .~ True

通过这种结构,我们甚至可以将整个过程立即升级为Statemonad.

flip execState initialDB $ do
  isFan "Joseph" "7 1/2"        .= True
  isFan "Steve"  "Citizen Kane" .= True
  -- oh, wait, nevermind
  isFan "Joseph" "7 1/2"        .= False

虽然,我们可以Control.Monad.State.withState使用任何定义来做同样的事情becomeFan.