英文:
Simple list concatenating function (intersperse) in Haskell
问题
我尝试编写一个 intersperse 函数，它接受一个包含 a 元素的列表（例如字符串列表）和一个单独的 a 元素（比如字符）作为分隔符，然后返回一个包含 a 元素或一个字符串的列表。
例如，如果我调用：
intersperse ',' ["a", "b"]
-- 我将得到 "a,b"
intersperse ',' ["hello"]
-- 我将只得到 "hello"
intersperse ',' ["a", "b", "c"]
-- 我将得到 "a,b,c"
intersperse 1 [[2,3,4], [5,6,7]]
-- 我将得到 [2, 3, 4, 1, 5, 6, 7]
intersperse 1 [[2,3], [4,5], [6,7]]
-- 我将得到 [2, 3, 1, 4, 5, 1, 6, 7]
所以我按照以下方式编写了它，它可以正常工作：
intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x:[]) = x
intersperse s (x:xs) = loop x xs
where loop a [] = a
loop a (x:xs) = loop (a ++ 展开收缩 ++ x) xs
但是如果我给循环函数添加类型签名，它将无法编译，我无法理解出错的原因。
intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x:[]) = x
intersperse s (x:xs) = loop x xs
where loop :: [a] -> [[a]] -> [a]
loop a [] = a
loop a (x:xs) = loop (a ++ 展开收缩 ++ x) xs
英文:
I'm trying to write an intersperse function that takes a list of lists of a e.g. a list of Strings, and one single a e.g. a char as a separator and returns a list of a or a String.
For example, if I call
intersperse ',' ["a", "b"]
-- I will get "a,b"
intersperse ',' ["hello"]
-- I will get only "hello"
intersperse ',' ["a", "b", "c"]
-- I will get "a,b,c"
intersperse 1 [[2,3,4], [5,6,7]]
-- I will get [2, 3, 4, 1, 5, 6, 7]
intersperse 1 [[2,3], [4,5], [6,7]]
-- I will get [2, 3, 1, 4, 5, 1, 6, 7]
--
So I wrote it as follows and it works fine.
intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x:[]) = x
intersperse s (x:xs) = loop x xs
where loop a [] = a
loop a (x:xs) = loop (a ++ 展开收缩 ++ x) xs
But if I add type signature to the loop function it will not compile, and I can't realise what's wrong
intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x:[]) = x
intersperse s (x:xs) = loop x xs
where loop :: [a] -> [[a]] -> [a]
loop a [] = a
loop a (x:xs) = loop (a ++ 展开收缩 ++ x) xs
答案1
得分: 1
> 但是如果我为循环函数添加类型签名，它将无法编译，我无法意识到问题出在哪里。
这是因为where子句中的a与顶层的a不同。您可以启用**ScopedTypeVariables**扩展 [ghc-doc]来解决这个问题：
<pre><code>{-# LANGUAGE <b>ScopedTypeVariables</b> #-}
intersperse :: <b>forall a.</b> a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x : []) = x
intersperse s (x : xs) = loop x xs
where
loop :: [a] -> [[a]] -> [a]
loop a [] = a
loop a (x : xs) = loop (a ++
intersperse 函数不是按需写的，这意味着对于大型列表，在结果交给调用者之前会花费很多时间，并且会消耗大量内存；对于无限列表，它会陷入一个无限循环，直到耗尽内存才会结束。
您可以通过以下方式优化该函数：
<pre><code>intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s [x] = x
intersperse s (x : xs) = x ++ go xs
where
go [] = []
go (x : xs) = <b>s : x ++ go xs</b></code></pre>
英文:
> But if I add type signature to the loop function it will not compile, and I can't realise what's wrong.
That is because the a in the where clause is a different one than the one at the top level. You can enable the ScopedTypeVariables extension [ghc-doc] for this:
<pre><code>{-# LANGUAGE <b>ScopedTypeVariables</b> #-}
intersperse :: <b>forall a.</b> a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x : []) = x
intersperse s (x : xs) = loop x xs
where
loop :: [a] -> [[a]] -> [a]
loop a [] = a
loop a (x : xs) = loop (a ++
The intersperse function is not written lazily however, this means that for large lists, it will take a lot of time before the result is handed to the caller, and will consume a lot of memory, and for infinite lists, it will get in an infinite loop that will end when memory is exhausted.
You can optimize the function with:
<pre><code>intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s [x] = x
intersperse s (x : xs) = x ++ go xs
where
go [] = []
go (x : xs) = <b>s : x ++ go xs</b></code></pre>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论