关于haskell:Lab-Exercises-for-COMP26020-Part-2

Lab Exercises for COMP26020 Part 2: Functional Programming in HaskellJoe Razavi December 8, 2023The deadline for this lab is 6pm on 16/2/2024.This lab has three exercises, for a total of ten marks. The first two exercises together are worth eight marks, and I advise all students to focus exclusively on these exercises. Seven marks are given based on automated testing, and one is reserved for human judgement by the marker. These exercises are described in Section 1 below. Section 2 contains submission information and a checklist of tasks for the first two exercises.If you are certain that your solutions are completely correct you might like to look at Section 3 below, which describes a thought-provoking, open-ended exercise requiring significant creativity, worth two marks. It is designed to be extremely difficult, and is not a practical way of gaining marks!1 Simple QuadtreesThis lab exercise concerns as data structure called a ‘quadtree’ which can be used to represent an image. There are sophisticated versions of the quadtree data structure, but for the purposes of the lab we will use a very simple version of the idea.Suppose we want to represent a square, black and white bitmap image which is2n by2n pixels. Theusualwaytodothisisasa2n by2n gridofbits,but this can be wasteful if there are large monochrome areas.1 ...

February 16, 2024 · 16 min · jiezi

关于haskell:Y-分钟速成-Haskell

源代码下载: learn-haskell-zh.hs Haskell 是一门实用的函数式编程语言,因其 Monads 与类型零碎而闻名。而我应用它则是因为它异样优雅。用 Haskell 编程令我感到十分高兴。 -- 单行正文以两个减号结尾{- 多行正文像这样 被一个闭合的块突围-}------------------------------------------------------ 1. 简略的数据类型和操作符------------------------------------------------------ 数字3 -- 3-- 数学计算1 + 1 -- 28 - 1 -- 710 * 2 -- 2035 / 5 -- 7.0-- 默认除法不是整除35 / 4 -- 8.75-- 整除35 `div` 4 -- 8-- 布尔值TrueFalse-- 布尔操作not True -- Falsenot False -- True1 == 1 -- True1 /= 1 -- False1 < 10 -- True-- 在下面的例子中,`not` 是一个承受一个参数的函数。-- Haskell 不须要括号来调用函数,所有的参数都只是在函数名之后列出来-- 因而,通常的函数调用模式是:-- func arg1 arg2 arg3...-- 你能够查看函数局部理解如何自行编写。-- 字符串和字符"This is a string." -- 字符串'a' -- 字符'对于字符串你不能应用单引号。' -- 谬误!-- 连贯字符串"Hello " ++ "world!" -- "Hello world!"-- 一个字符串是一系列字符['H', 'e', 'l', 'l', 'o'] -- "Hello""This is a string" !! 0 -- 'T'------------------------------------------------------ 2. 列表和元组------------------------------------------------------ 一个列表中的每一个元素都必须是雷同的类型。-- 上面两个列表等价[1, 2, 3, 4, 5][1..5]-- 区间也能够这样['A'..'F'] -- "ABCDEF"-- 你能够在区间中指定步进[0,2..10] -- [0, 2, 4, 6, 8, 10][5..1] -- 这样不行,因为 Haskell 默认递增[5,4..1] -- [5, 4, 3, 2, 1]-- 列表下标[0..] !! 5 -- 5-- 在 Haskell 你能够应用有限列表[1..] -- 一个含有所有自然数的列表-- 有限列表的原理是,Haskell 有“惰性求值”。-- 这意味着 Haskell 只在须要时才会计算。-- 所以当你获取列表的第 1000 项元素时,Haskell 会返回给你:[1..] !! 999 -- 1000-- Haskell 计算了列表中第 1 至 1000 项元素,但这个有限列表中剩下的元素还不存在。-- Haskell 只有在须要时才会计算它们。-- 连贯两个列表[1..5] ++ [6..10]-- 往列表头减少元素0:[1..5] -- [0, 1, 2, 3, 4, 5]-- 其它列表操作head [1..5] -- 1tail [1..5] -- [2, 3, 4, 5]init [1..5] -- [1, 2, 3, 4]last [1..5] -- 5-- 列表推导 (list comprehension)[x*2 | x <- [1..5]] -- [2, 4, 6, 8, 10]-- 附带条件[x*2 | x <-[1..5], x*2 > 4] -- [6, 8, 10]-- 元组中的每一个元素能够是不同类型,然而一个元组的长度是固定的-- 一个元组("haskell", 1)-- 获取元组中的元素(例如,一个含有 2 个元素的元祖)fst ("haskell", 1) -- "haskell"snd ("haskell", 1) -- 1------------------------------------------------------ 3. 函数------------------------------------------------------ 一个承受两个变量的简略函数add a b = a + b-- 留神,如果你应用 ghci (Haskell 解释器),你须要应用 `let`,也就是-- let add a b = a + b-- 调用函数add 1 2 -- 3-- 你也能够应用反引号中置函数名:1 `add` 2 -- 3-- 你也能够定义不带字母的函数名,这样你能够定义本人的操作符。-- 这里有一个做整除的操作符(//) a b = a `div` b35 // 4 -- 8-- Guard:一个在函数中做条件判断的简略办法fib x | x < 2 = x | otherwise = fib (x - 1) + fib (x - 2)-- 模式匹配与 Guard 相似。-- 这里给出了三个不同的 fib 定义。-- Haskell 会主动调用第一个合乎参数模式的申明fib 1 = 1fib 2 = 2fib x = fib (x - 1) + fib (x - 2)-- 元组的模式匹配foo (x, y) = (x + 1, y + 2)-- 列表的模式匹配-- 这里 `x` 是列表中第一个元素,`xs` 是列表残余的局部。-- 咱们能够实现本人的 map 函数:myMap func [] = []myMap func (x:xs) = func x:(myMap func xs)-- 匿名函数带有一个反斜杠,前面跟着所有的参数myMap (\x -> x + 2) [1..5] -- [3, 4, 5, 6, 7]-- 在 fold(在一些语言称 为`inject`)中应用匿名函数-- foldl1 意味着左折叠 (fold left), 并且应用列表中第一个值作为累加器的初始值。foldl1 (\acc x -> acc + x) [1..5] -- 15------------------------------------------------------ 4. 其它函数------------------------------------------------------ 局部调用-- 如果你调用函数时没有给出所有参数,它就被“局部调用”。-- 它将返回一个承受余下参数的函数。add a b = a + bfoo = add 10 -- foo 当初是一个承受一个数并对其加 10 的函数foo 5 -- 15-- 另一种等价写法foo = (+10)foo 5 -- 15-- 函列表合-- (.) 函数把其它函数链接到一起。-- 例如,这里 foo 是一个承受一个值的函数。-- 它对承受的值加 10,并对后果乘以 5,之后返回最初的值。foo = (*5) . (+10)-- (5 + 10) * 5 = 75foo 5 -- 75-- 修改优先级-- Haskell 有另外一个函数 `$` 能够扭转优先级。-- `$` 使得 Haskell 先计算其左边的局部,而后调用右边的局部。-- 你能够应用 `$` 来移除多余的括号。-- 批改前(even (fib 7)) -- False-- 批改后even . fib $ 7 -- False-- 等价地even $ fib 7 -- False------------------------------------------------------ 5. 类型申明------------------------------------------------------ Haskell 有一个十分弱小的类型零碎,所有都有一个类型申明。-- 一些根本的类型:5 :: Integer"hello" :: StringTrue :: Bool-- 函数也有类型-- `not` 承受一个布尔型返回一个布尔型-- not :: Bool -> Bool-- 这是承受两个参数的函数-- add :: Integer -> Integer -> Integer-- 当你定义一个值,申明其类型是一个好做法double :: Integer -> Integerdouble x = x * 2------------------------------------------------------ 6. 控制流和 If 语句------------------------------------------------------ if 语句:haskell = if 1 == 1 then "awesome" else "awful" -- haskell = "awesome"-- if 语句也能够有多行,留神缩进:haskell = if 1 == 1 then "awesome" else "awful"-- case 语句-- 解析命令行参数:case args of "help" -> printHelp "start" -> startProgram _ -> putStrLn "bad args"-- Haskell 没有循环,它应用递归-- map 对一个列表中的每一个元素调用一个函数map (*2) [1..5] -- [2, 4, 6, 8, 10]-- 你能够应用 map 来编写 for 函数for array func = map func array-- 调用for [0..5] $ \i -> show i-- 咱们也能够像这样写for [0..5] show-- 你能够应用 foldl 或者 foldr 来合成列表-- foldl <fn> <initial value> <list>foldl (\x y -> 2*x + y) 4 [1,2,3] -- 43-- 等价于(2 * (2 * (2 * 4 + 1) + 2) + 3)-- foldl 从左开始,foldr 从右foldr (\x y -> 2*x + y) 4 [1,2,3] -- 16-- 当初它等价于(2 * 3 + (2 * 2 + (2 * 1 + 4)))------------------------------------------------------ 7. 数据类型------------------------------------------------------ 在 Haskell 中申明你本人的数据类型:data Color = Red | Blue | Green-- 当初你能够在函数中应用它:say :: Color -> Stringsay Red = "You are Red!"say Blue = "You are Blue!"say Green = "You are Green!"-- 你的数据类型也能够有参数:data Maybe a = Nothing | Just a-- 这些都是 Maybe 类型:Just "hello" -- `Maybe String` 类型Just 1 -- `Maybe Int` 类型Nothing -- 对任意 `a` 为 `Maybe a` 类型------------------------------------------------------ 8. Haskell IO------------------------------------------------------ 尽管不解释 Monads 就无奈齐全解释 IO,但大抵理解并不难。-- 当执行一个 Haskell 程序时,函数 `main` 就被调用。-- 它必须返回一个类型 `IO ()` 的值。例如:main :: IO ()main = putStrLn $ "Hello, sky! " ++ (say Blue) -- putStrLn 的类型是 String -> IO ()-- 如果你的程序输出 String 返回 String,那样编写 IO 是最简略的。-- 函数-- interact :: (String -> String) -> IO ()-- 输出一些文本,对其调用一个函数,并打印输出。countLines :: String -> StringcountLines = show . length . linesmain' = interact countLines-- 你能够认为一个 `IO ()` 类型的值是示意计算机做的一系列操作,相似命令式语言。-- 咱们能够应用 `do` 申明来把动作连贯到一起。-- 举个列子sayHello :: IO ()sayHello = do putStrLn "What is your name?" name <- getLine -- 这里承受一行输出并绑定至 "name" putStrLn $ "Hello, " ++ name -- 练习:编写只读取一行输出的 `interact` -- 然而,`sayHello` 中的代码将不会被执行。惟一被执行的动作是 `main` 的值。-- 为了运行 `sayHello`,正文下面 `main` 的定义,替换为:-- main = sayHello-- 让咱们来更进一步了解方才所应用的函数 `getLine` 是怎么工作的。它的类型是:-- getLine :: IO String-- 你能够认为一个 `IO a` 类型的值代表了一个运行时会生成一个 `a` 类型值的程序。-- (可能随同其它行为)-- 咱们能够通过 `<-` 保留和重用这个值。-- 咱们也能够实现本人的 `IO String` 类型函数:action :: IO Stringaction = do putStrLn "This is a line. Duh" input1 <- getLine input2 <- getLine -- `do` 语句的类型是它的最初一行 -- `return` 不是关键字,只是一个一般函数 return (input1 ++ "\n" ++ input2) -- return :: String -> IO String-- 咱们能够像调用 `getLine` 一样调用它main'' = do putStrLn "I will echo two lines!" result <- action putStrLn result putStrLn "This was all, folks!"-- `IO` 类型是一个 "Monad" 的例子。-- Haskell 通过应用 Monad 使得其自身为纯函数式语言。-- 任何与外界交互的函数(即 IO)都在它的类型申明中标记为 `IO`。-- 这通知咱们什么样的函数是“纯净的”(不与外界交互,不批改状态) ,-- 什么样的函数不是 “纯净的”。-- 这个性能十分弱小,因为纯函数并发非常容易,由此在 Haskell 中做并发非常容易。------------------------------------------------------ 9. Haskell REPL------------------------------------------------------ 键入 `ghci` 开始 REPL。-- 当初你能够键入 Haskell 代码。-- 任何新值都须要通过 `let` 来创立let foo = 5-- 你能够通过命令 `:t` 查看任何值的类型>:t foofoo :: Integer-- 你也能够运行任何 `IO ()`类型的动作> sayHelloWhat is your name?Friend!Hello, Friend!Haskell 还有许多内容,包含类型类 (typeclasses) 与 Monads。这些都是令 Haskell 编程十分乏味的好货色。咱们最初给出 Haskell 的一个例子,一个疾速排序的实现: ...

November 28, 2022 · 5 min · jiezi

关于haskell:Haskell-Monoid幺半群的介绍

翻译自 https://gist.github.com/cscal...为什么程序员应该关怀 Monoids?因为 Monoids 是一种在编程中重复呈现的常见模式。当模式呈现时,咱们能够将它们抽象化并利用咱们过来所做的工作。这使咱们可能在通过验证的稳固代码之上疾速开发解决方案。 将"可替换性"增加到 Monoid(Commutative Monoid),你就有了能够并行执行的货色。随着摩尔定律的终结,并行计算是咱们进步处理速度的惟一心愿。 以下是我在学习 Monoids 后学到的。它未必残缺,但心愿可能对于向人们介绍 Monoids 有所帮忙。 Monoid 谱系Monoid 来自数学,从属于代数构造的谱系。因而,从头开始并逐渐开展到 Monoids 会有所帮忙。 实际上,咱们进一步能够推到"群"(Groups). Magma(元群)Magma 是一个汇合以及一个必须闭合的二元运算: ∀ a, b ∈ M : a • b ∈ M如果将二元运算利用于汇合的任意 2 个元素时,它会生成汇合的另一个成员,则该二元运算是关闭的。 (这里 · 示意二元运算) Magma 的一个示例是 Boolean 和 AND 运算的汇合。 Semigroup(半群)Semigroup 是具备一个附加要求的 Magma。二元运算对于汇合的所有成员必须是"可联合"的: ∀ a, b, c ∈ S : a · (b · c) = (a · b) · c一个 Semigroup 的例子是"非空字符串"和"字符串拼接"运算的汇合。 Monoid(幺半群)Monoid 是蕴含一个附加条件的 Semigroup。汇合中存在一个"幺元"(Neutral Element),能够应用二元运算将其与汇合的任何成员联合,而产生属于雷同汇合的成员。 ...

April 21, 2022 · 8 min · jiezi

关于haskell:Expression-Problem-和-Calcit-相关引用笔记

Wiki https://en.wikipedia.org/wiki...知乎援用 https://www.zhihu.com/questio...中文简介 http://mgampkay.github.io/pos...The Expression Problem and its solutionsMore thoughts on the Expression Problem in Haskell3 ways to solve the expression problemThe Expression Problem in RustSolving the Expression Problem with Clojure(Protocol)Calcit 示例代码 ns app.maindefrecord %expr-methods :evaldef %const $ %{} %expr-methods :eval $ fn (tp) nth tp 1def %binary-plus $ %{} %expr-methods :eval $ fn (tp) &let pair $ nth tp 1 + (nth pair 0) (nth pair 1)def %const-2 $ .extend-as %const '%const-2 , :stringify $ fn (tp) str "|(Const " (nth tp 1) "| )"def %binary-plus-2 $ .extend-as %binary-plus '%binary-plus-2' , :stringify $ fn (tp) &let pair $ nth tp 1 str "|(BinaryPlus " (first pair) "| " (last pair) "| )"defn main () echo $ .eval $ :: %const 1 echo $ .eval $ :: %binary-plus $ [] 1 2 echo $ .stringify $ :: %const-2 1 echo $ .eval $ :: %const-2 1 echo $ .stringify $ :: %binary-plus-2 $ [] 1 2 echo $ .eval $ :: %binary-plus-2 $ [] 1 2运行示例: ...

August 10, 2021 · 1 min · jiezi

关于haskell:一种-Monad-的偏门的理解方式

我对数学概念属性符号把握得不好, 所以了解比较慢,这篇文章是从概念性的内容去了解 Monad, 不准确, 可能具体到数学概念也不精确.然而心愿提供一个比拟直观的形式去理解, Monad 是怎么来的? 概念上简略说 Monad 是"自函子领域上的一个幺半群".新概念很多, 函子, 自函子, 领域, 半群, 幺半群.模糊地讲, 这些就是数学的概念, 汇合啦, 汇合元素间的映射啦, 单位元啦, Monad 概念含糊了解的话, 函子能够当做是函数, a -> b 的映射, 当然也能够比函数更形象点的货色,而后"自函子", 波及到类型的概念, 函子从一个汇合 A 到另一个汇合 B,但咱们把程序所有货色都放在一起的话, 函子能够认为是从 A 到 A 本人了, 所以是"自函子"."领域"我解释不来, 大抵是这些函子的形成和关系, 具体看何幻的文章.从后面这部分看, Haskell 把程序当成各种汇合还有映射来对待了,程序中, 无论值的变动, 甚至副作用的变动, 全都纳入到领域里边来了解. 而后幺半群呢? 要了解这些概念, 就要晓得相干的几个概念, 原群(Magma)一个汇合, 而后汇合上的元素的二元操作, 操作后果都在这个汇合外部,一个例子, 比方 { true false }, 还有二元操作 and or,任何二元操作的后果都在汇合内. 半群(Semigroup)半群在原群的根底上减少了一个条件, 满足结合律:比方所有非空的字符串的汇合, 以及 concat 操作."a" `concat` "b" 失去 "ab" 还在汇合内,而后 ("a" `concat` "b") `concat` "c" 失去 "abc",而后 "a" `concat` ("b" `concat` "c") 失去 "abc",两者是等价的, 满足结合律. ...

March 16, 2021 · 3 min · jiezi